Leetcode 436 - Find Right Interval

Note:

  • Use map to store original indexes.
  • Then sort it based on start.
  • For each $end_i$, find the first $start_j$ that $start_j > end_i$.
  • Apparently, if we use binary search, we can finish in O(logn).

Question:

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
2
3
4
5
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.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* @param {number[][]} intervals
* @return {number[]}
*/
var findRightInterval = function(intervals) {
let map = new Map();
for (const [i, [a, b]] of intervals.entries()) {
map.set(a + '.' + b, i);
}
intervals.sort((a, b) => a[0] - b[0]);
let ans = [...new Array(intervals.length).fill(-1)];
for (let i = 0; i < intervals.length; i++) {
const index = map.get(intervals[i][0] + '.' + intervals[i][1]);
let j = i;
let left = i, right = intervals.length - 1;
while (left < right) {
const mid = (left + right) >> 1;
if (intervals[mid][0] < intervals[i][1]) {
left = mid + 1;
} else {
right = mid;
}
}
if (intervals[left][0] >= intervals[i][1]) {
ans[index] = map.get(intervals[left][0] + '.' + intervals[left][1]);
} else {
ans[index] = -1;
}
}
return ans;
};