Problem
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. Note that i may equal j.
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 * 10^4intervals[i].length == 2-10^6 <= starti <= endi <= 10^6The start point of each interval is unique.
Solution (Java)
class Solution {
private int[] findminmax(int[][] num) {
int min = num[0][0];
int max = num[0][0];
for (int i = 1; i < num.length; i++) {
min = Math.min(min, num[i][0]);
max = Math.max(max, num[i][0]);
}
return new int[] {min, max};
}
public int[] findRightInterval(int[][] intervals) {
if (intervals.length <= 1) {
return new int[] {-1};
}
int n = intervals.length;
int[] result = new int[n];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(intervals[i][0], i);
}
int[] minmax = findminmax(intervals);
for (int i = minmax[1] - 1; i >= minmax[0] + 1; i--) {
map.computeIfAbsent(i, k -> map.get(k + 1));
}
for (int i = 0; i < n; i++) {
result[i] = map.getOrDefault(intervals[i][1], -1);
}
return result;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).