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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
private static class Interval implements Comparable<Interval> {
private final int start;
private final int end;
private final int index;
public Interval(int start, int end, int index) {
this.start = start;
this.end = end;
this.index = index;
}
@Override
public int compareTo(Interval o) {
return Integer.compare(start, o.start);
}
}
public int[] findRightInterval(int[][] intervals) {
Interval[] intervalArray = new Interval[intervals.length];
for (int i = 0; i < intervals.length; i++) {
intervalArray[i] = new Interval(intervals[i][0], intervals[i][1], i);
}
Arrays.sort(intervalArray);
int[] res = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
res[i] = binarySearch(intervalArray, intervals[i][1]);
}
return res;
}
private int binarySearch(Interval[] intervalArray, int target) {
int left = 0, right = intervalArray.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (intervalArray[mid].start < target) {
left = mid + 1;
} else if (intervalArray[mid].start > target) {
right = mid;
} else {
return intervalArray[mid].index;
}
}
return left == intervalArray.length ? -1 : intervalArray[left].index;
}
}
|