436.寻找右区间.md

436.寻找右区间

/*
 * @lc app=leetcode.cn id=436 lang=typescript
 *
 * [436] 寻找右区间
 */

// @lc code=start
function findRightInterval(a: [number, number][]): number[] {}
// @lc code=end

解法 1: 排序 + 二分

function findRightInterval(a: [number, number][]): number[] {
  const b = a.map((arr, i) => [...arr, i])
  b.sort((a, b) => a[0] - b[0])
  const res: number[] = []
  for (let [j, [st, en, i]] of b.entries()) {
    let l = j,
      r = b.length - 1
    while (l < r) {
      const mid = (l + r) >> 1
      if (b[mid][0] >= en) {
        r = mid
      } else {
        l = mid + 1
      }
    }
    if (b[l][0] >= en) {
      res[i] = b[l][2]
    } else {
      res[i] = -1
    }
  }
  return res
}

Case

test.each([
  { input: { intervals: [[1, 2]] }, output: [-1] },
  {
    input: {
      intervals: [
        [3, 4],
        [2, 3],
        [1, 2],
      ],
    },
    output: [-1, 0, 1],
  },
  {
    input: {
      intervals: [
        [1, 4],
        [2, 3],
        [3, 4],
      ],
    },
    output: [-1, 2, -1],
  },
])('input: intervals = $input.intervals', ({ input: { intervals }, output }) => {
  expect(findRightInterval(intervals)).toEqual(output)
})