Find Right Interval

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.

Examples

Example 1:

1
2
3
4
5


Input:
intervals = [[1,2]]
Output:
 [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

1
2
3
4
5
6
7


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:

1
2
3
4
5
6


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.

Solution

Method 1 - Binary Search on Sorted Start Times

Intuition

For each interval, we want to find the interval with the smallest start time that is greater than or equal to its end time. By sorting the intervals by start time and using binary search, we can efficiently find the right interval for each query.

Approach

Store the start times and their original indices.
Sort the start times.
For each interval, use binary search to find the smallest start time that is >= the end time.
If found, record the index; otherwise, record -1.

Code

1
2

##### C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<pair<int, int>> starts;
        for (int i = 0; i < n; ++i) {
            starts.emplace_back(make_pair(intervals[i][0], i));
        }
        sort(starts.begin(), starts.end());
        vector<int> res;
        for (auto interval : intervals) {
            int left = 0, right = n - 1;
            int end = interval[1];
            while (left < right) {
                int mid = left + right >> 1;
                if (starts[mid].first >= end)
                    right = mid;
                else
                    left = mid + 1;
            }
            res.push_back(starts[left].first < end ? -1 : starts[left].second);
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


func findRightInterval(intervals [][]int) []int {
    n := len(intervals)
    starts := make([][]int, n)
    for i := 0; i < n; i++ {
        starts[i] = make([]int, 2)
        starts[i][0] = intervals[i][0]
        starts[i][1] = i
    }
    sort.Slice(starts, func(i, j int) bool {
        return starts[i][0] < starts[j][0]
    })
    var res []int
    for _, interval := range intervals {
        left, right, end := 0, n-1, interval[1]
        for left < right {
            mid := (left + right) >> 1
            if starts[mid][0] >= end {
                right = mid
            } else {
                left = mid + 1
            }
        }
        val := -1
        if starts[left][0] >= end {
            val = starts[left][1]
        }
        res = append(res, val)
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        List<int[]> starts = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            starts.add(new int[] {intervals[i][0], i});
        }
        starts.sort(Comparator.comparingInt(a -> a[0]));
        int[] res = new int[n];
        int i = 0;
        for (int[] interval : intervals) {
            int left = 0, right = n - 1;
            int end = interval[1];
            while (left < right) {
                int mid = (left + right) >> 1;
                if (starts.get(mid)[0] >= end) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            res[i++] = starts.get(left)[0] < end ? -1 : starts.get(left)[1];
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    fun findRightInterval(intervals: Array<IntArray>): IntArray {
        val n = intervals.size
        val starts = Array(n) { intArrayOf(intervals[it][0], it) }
        starts.sortBy { it[0] }
        val res = IntArray(n)
        for ((idx, interval) in intervals.withIndex()) {
            var left = 0
            var right = n - 1
            val end = interval[1]
            while (left < right) {
                val mid = (left + right) shr 1
                if (starts[mid][0] >= end) {
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            res[idx] = if (starts[left][0] < end) -1 else starts[left][1]
        }
        return res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        for i, v in enumerate(intervals):
            v.append(i)
        intervals.sort()
        n = len(intervals)
        ans = [-1] * n
        for _, e, i in intervals:
            j = bisect_left(intervals, [e])
            if j < n:
                ans[i] = intervals[j][2]
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


impl Solution {
    pub fn find_right_interval(intervals: Vec<Vec<i32>>) -> Vec<i32> {
        let n = intervals.len();
        let mut starts: Vec<(i32, usize)> = intervals.iter().enumerate().map(|(i, v)| (v[0], i)).collect();
        starts.sort_by_key(|x| x.0);
        let mut res = Vec::with_capacity(n);
        for interval in &intervals {
            let end = interval[1];
            let mut left = 0;
            let mut right = n - 1;
            while left < right {
                let mid = (left + right) / 2;
                if starts[mid].0 >= end {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            if starts[left].0 < end {
                res.push(-1);
            } else {
                res.push(starts[left].1 as i32);
            }
        }
        res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


function findRightInterval(intervals: number[][]): number[] {
    const n = intervals.length;
    const starts = Array.from({ length: n }).map(() => new Array<number>(2));
    for (let i = 0; i < n; i++) {
        starts[i][0] = intervals[i][0];
        starts[i][1] = i;
    }
    starts.sort((a, b) => a[0] - b[0]);

    return intervals.map(([_, target]) => {
        let left = 0;
        let right = n;
        while (left < right) {
            const mid = (left + right) >>> 1;
            if (starts[mid][0] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (left >= n) {
            return -1;
        }
        return starts[left][1];
    });
}

Complexity

⏰ Time complexity: O(n log n)
- Sorting the intervals by start time takes O(n log n).
- For each interval, we perform a binary search in O(log n), so total is O(n log n).
🧺 Space complexity: O(n)
- We store the start times and indices in an auxiliary array of size n.

Problem#

Examples#

Solution#

Method 1 - Binary Search on Sorted Start Times#

Intuition#

Approach#

Code#

Complexity#