Find Right Interval

Given a list of intervals intervals, where intervals[i] = [start_i, end_i], for each interval i, find the index of the interval j such that start_j is the smallest possible value that is equal to or greater than end_i. If there is no such interval j, the output should be -1.

The output for each interval i should be the index j, and if multiple valid answers exist, you need to return the smallest of them.

Sample Input/Output:

Let’s consider a sample input:

intervals = [[1, 2], [2, 3], [0, 1], [3, 4]]

Expected Output:

[-1, 2, 1, -1]

Explanation:
For interval [1, 2] (index 0), there is no interval with start_j >= end_i, so the output is -1.

For interval [2, 3] (index 1), the interval [3, 4] (index 3) has the smallest possible start value greater than or equal to end_i, so the output is 3 (index of [3, 4]).

For interval [0, 1] (index 2), the interval [1, 2] (index 0) has the smallest possible start value greater than or equal to end_i, so the output is 0 (index of [1, 2]).

For interval [3, 4] (index 3), there is no interval with start_j >= end_i, so the output is -1.

Time and Space Complexity:

The time complexity of the solution will be O(N log N) due to the sorting of the intervals based on their start values.

The space complexity will be O(N) to store the sorted intervals and the result vector.

Now, let’s implement the solution in C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector<int> findRightInterval(vector<vector<int>>& intervals) {
    vector<int> result;
    map<int, int> startToIndex;

    // Populate a map with the start value as the key and the index as the value
    for (int i = 0; i < intervals.size(); ++i) {
        startToIndex[intervals[i][0]] = i;
    }

    for (const auto& interval : intervals) {
        auto it = startToIndex.lower_bound(interval[1]);
        if (it != startToIndex.end()) {
            result.push_back(it->second);
        } else {
            result.push_back(-1);
        }
    }

    return result;
}

int main() {
    vector<vector<int>> intervals = {{1, 2}, {2, 3}, {0, 1}, {3, 4}};
    vector<int> result = findRightInterval(intervals);

    cout << "Right Intervals:\n";
    for (int index : result) {
        cout << index << " ";
    }
    cout << endl;

    return 0;
}

In this implementation, we use a map to store the start values of the intervals as keys and their corresponding indices as values.

The findRightInterval function iterates through each interval and uses lower_bound to find the smallest start value greater than or equal to the current interval’s end value. If a valid interval is found, its index is pushed into the result vector; otherwise, -1 is pushed.

The main function demonstrates the usage of findRightInterval by finding the right intervals for the given input intervals.

The output for the provided test case will be:

Right Intervals:
-1 2 1 -1