LeetCode Solutions
436. Find Right Interval
Time: $O(n\log n)$ Space: $O(n)$
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
vector<int> ans;
map<int, int> startToIndex;
for (int i = 0; i < intervals.size(); ++i)
startToIndex[intervals[i][0]] = i;
for (const vector<int>& interval : intervals) {
const auto it = startToIndex.lower_bound(interval[1]);
if (it == cend(startToIndex))
ans.push_back(-1);
else
ans.push_back(it->second);
}
return ans;
}
};
class Solution {
public int[] findRightInterval(int[][] intervals) {
final int n = intervals.length;
int[] ans = new int[n];
java.util.NavigableMap<Integer, Integer> startToIndex = new TreeMap<>();
for (int i = 0; i < n; ++i)
startToIndex.put(intervals[i][0], i);
for (int i = 0; i < n; ++i) {
Map.Entry<Integer, Integer> entry = startToIndex.ceilingEntry(intervals[i][1]);
if (entry == null)
ans[i] = -1;
else
ans[i] = entry.getValue();
}
return ans;
}
}