Find Right Interval

Description

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

 

Example 1:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Example 3:

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

 

Constraints:

• 1 <= intervals.length <= 2 * 104
• intervals[i].length == 2
• -106 <= starti <= endi <= 106
• The start point of each interval is unique.

Solution(javascript)

/*
 * @lc app=leetcode id=436 lang=javascript
 *
 * [436] Find Right Interval
 */

// @lc code=start
/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
const findRightInterval = function (intervals) {
  intervals = intervals.map((x, index) => [...x, index])
    .sort((a, b) => {
      if (a[0] === b[0]) {
        if (a[1] === b[1]) {
          return a[2] - b[2]
        }
        return a[1] - b[1]
      }
      return a[0] - b[0]
    })
  const search = (left, target) => {
    let right = intervals.length - 1
    let result = -1
    while (left <= right) {
      const middle = Math.floor(left + (right - left) / 2)
      if (intervals[middle][0] >= target[1]) {
        result = middle
        right = middle - 1
      } else {
        left = middle + 1
      }
    }
    return result
  }
  const result = []
  for (let i = 0; i < intervals.length; i++) {
    const index = search(i + 1, intervals[i])
    if (index === -1) {
      result[intervals[i][2]] = -1
    } else {
      result[intervals[i][2]] = intervals[index][2]
    }
  }
  return result
}
// @lc code=end