algoadvance

Leetcode 436. Find Right Interval

Problem Statement

Given a collection of intervals, find the minimum interval’s index for each interval such that the start point of this interval is greater than or equal to the end point of the given interval. If no such interval exists, return -1.

You may assume intervals’ end points are all unique.

Example:

Given interval list intervals:

[ [1,2], [2,3], [3,4] ]

For each interval, you need to output the index of the minimum interval that has a start point greater than or equal to the end point of the current interval. Therefore, the output should be:

[-1, 0, 1]

Clarifying Questions

1. Q: Can the intervals be overlapping? A: Yes.

2. Q: Are the intervals guaranteed to be sorted? A: No, intervals are not guaranteed to be sorted.

3. Q: What is the range of the interval values? A: The interval values are arbitrary integers, but you can assume a reasonable constraint such that they fit within typical integer ranges.

4. Q: Is there any restriction on the size of the input array? A: The size of the intervals array is not explicitly restricted, but it can be assumed to fit within the constraints of typical coding interview problems (e.g., up to thousands of intervals).

Strategy

1. Data Representation: Use tuples to store the intervals along with their original indices.
2. Sorting: Sort the array of tuples based on the start time for efficient searching.
3. Binary Search: For each interval, perform a binary search to find the interval with the minimum start time that is greater than or equal to the current interval’s end time.
4. Index Mapping: Map the search results back to the original indices.

Steps to Solve:

1. Create a vector of tuples where each tuple contains the start time, end time, and original index of each interval.
2. Sort this vector based on the start times.
3. For each interval in the original list, use binary search on the sorted list to find the smallest interval start time that is greater than or equal to the interval’s end time.
4. Map the found index to the original index and store the result.
5. Return the result list.

Code

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> findRightInterval(vector<vector<int>>& intervals) {
    int n = intervals.size();
    vector<tuple<int, int, int>> sortedIntervals;
    
    // Step 1: Create tuples of (start, end, index)
    for (int i = 0; i < n; i++) {
        sortedIntervals.emplace_back(intervals[i][0], intervals[i][1], i);
    }
    
    // Step 2: Sort tuples by start times
    sort(sortedIntervals.begin(), sortedIntervals.end());
    
    vector<int> result(n, -1);
    
    // Step 3: Perform binary search for each interval
    for (int i = 0; i < n; i++) {
        int end = intervals[i][1];
        int lo = 0, hi = n - 1;
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (get<0>(sortedIntervals[mid]) < end) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        if (get<0>(sortedIntervals[lo]) >= end) {
            result[i] = get<2>(sortedIntervals[lo]);
        } else {
            result[i] = -1;
        }
    }
    
    return result;
}

int main() {
    vector<vector<int>> intervals = \{\{1, 2}, {2, 3}, {3, 4}};
    vector<int> result = findRightInterval(intervals);
    for (int idx : result) {
        cout << idx << " ";
    }
    cout << endl;
    return 0;
}

Time Complexity

• Sorting: O(n log n) because we sort the intervals based on their start times.
• Binary Search: O(log n) for each interval (we do this n times).

Overall, the time complexity is O(n log n).

Additional Notes

• This approach leverages sorting and binary search to make the interval lookup efficient.
• It ensures that even large inputs will be handled within reasonable time bounds given typical constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?