Find Right Interval

Problem

For each interval i, find the smallest j whose start ≥ end of i; return -1 if none. Return the answer array.

Constraints

• 1 ≤ n ≤ 2·10⁴

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

class Solution:
    def findRightInterval(self, intervals):
        import bisect
        starts = sorted((iv[0], i) for i, iv in enumerate(intervals))
        keys = [s for s, _ in starts]
        res = []
        for iv in intervals:
            pos = bisect.bisect_left(keys, iv[1])
            res.append(starts[pos][1] if pos < len(starts) else -1)
        return res

Java

import java.util.*;
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] starts = new int[n][2];
        for (int i = 0; i < n; i++) starts[i] = new int[]{intervals[i][0], i};
        Arrays.sort(starts, (a, b) -> a[0] - b[0]);
        int[] out = new int[n];
        for (int i = 0; i < n; i++) {
            int end = intervals[i][1];
            int lo = 0, hi = n;
            while (lo < hi) {
                int m = lo + (hi - lo) / 2;
                if (starts[m][0] < end) lo = m + 1;
                else                     hi = m;
            }
            out[i] = lo == n ? -1 : starts[lo][1];
        }
        return out;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.