The problem involves finding the smallest "right interval" for each interval in a given list of intervals. A "right interval" for an interval [start, end] is an interval [start2, end2] such that start2 ≥ end.
The solution involves sorting the intervals by their start times and using binary search to efficiently find the right interval for each interval.
class Solution {
public int[] findRightInterval(int[][] intervals) {
int n = intervals.length;
int[] result = new int[n];
TreeMap<Integer, Integer> map = new TreeMap<>(); // Stores start time and its index
// Step 1: Store start times and their indices in TreeMap
for (int i = 0; i < n; i++) {
map.put(intervals[i][0], i);
}
// Step 2: Find the right interval for each interval
for (int i = 0; i < n; i++) {
Integer key = map.ceilingKey(intervals[i][1]); // Find the smallest start time >= end time
result[i] = (key != null) ? map.get(key) : -1;
}
return result;
}
}O(log n) – Each lookup or insertion in the TreeMap takes logarithmic time.O(n log n) – For n intervals, inserting into the TreeMap and performing lookups.Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1, 0, 1]
Explanation:
- For interval [3,4], there is no right interval, so the output is -1.
- For interval [2,3], the right interval is [3,4] (index 0).
- For interval [1,2], the right interval is [2,3] (index 1).