Find Right Interval
Medium · Binary Search · Explanation and code example
Ordered Starts and Lower Bound
How it works
For each interval end, find the smallest start value at least as large as that end. Store original indices alongside sorted starts. Python uses binary search over sorted pairs; C++ uses an ordered map’s lower_bound to perform the same successor query.
Steps
- Index each interval’s start.
- Build the sorted starts or ordered map.
- For each end, return the first qualifying start’s original index, or -1.
Complexity
- Time: O(n log n).
- Space: O(n).
Things to watch for
- Equality qualifies, so use lower_bound rather than upper_bound.
- Return original indices, rather than sorted positions.
- An interval with start == end can point to itself.
Python code example
from bisect import bisect_left
class Solution:
def findRightInterval(self, intervals: list[list[int]]) -> list[int]:
starts = sorted((start, index) for index, (start, _) in enumerate(intervals))
values = [start for start, _ in starts]
result = []
for _, end in intervals:
index = bisect_left(values, end)
result.append(starts[index][1] if index < len(starts) else -1)
return result
C++ code example
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]);
ans.push_back(it == startToIndex.cend() ? -1 : it->second);
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.