The task requires identifying, for each given range [start, end], another range whose starting point is greater than or equal to the current range's ending point. Among all valid candidates, the one with the smallest starting value must be selected. The original index of this matching range is returned, or -1 if no such range exists. A critical detail is that a range can match itself if its start equals its end.

Given the constraint that all starting points are unique and the array size reaches up to 2 * 10^4, an O(n^2) linear scan per interval will exceed time limits. Sorting the starting points enables an O(n log n) solution via binary search. The primary challenge lies in preserving the original indices after sorting.

Index Preservation and Manual Binary Search

The most direct method involves creating a separate collection that pairs each starting value with its original position. After sorting this collection by start values, iterate through the original intervals. For each interval's end value, perform a binary search on the sorted starts to locate the first vallue that satisfies the condition.

#include <vector>
#include <algorithm>

class IntervalResolver {
public:
    std::vector<int> locateRightIntervals(std::vector<std::vector<int>>& ranges) {
        int count = ranges.size();
        std::vector<std::pair<int, int>> startPoints(count);

        for (int idx = 0; idx < count; ++idx) {
            startPoints[idx] = {ranges[idx][0], idx};
        }

        std::sort(startPoints.begin(), startPoints.end());

        std::vector<int> results(count, -1);

        for (int i = 0; i < count; ++i) {
            int threshold = ranges[i][1];
            int left = 0;
            int right = count - 1;
            int matchIdx = -1;

            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (startPoints[mid].first >= threshold) {
                    matchIdx = startPoints[mid].second;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            results[i] = matchIdx;
        }

        return results;
    }
};

This implementation explicitly tracks the search boundaries and updates the potential match whenever a valid start point is found, continuing leftward to ensure minimization.

Standard Library Optimization

C++ provides std::lower_bound, which inherently performs a binary search to find the first element that does not compare less than a given value. By constructing a vector of pairs containing only the start values and their original indices, the lookup logic becomes significantly more compact.

#include <vector>
#include <algorithm>

class IntervalResolver {
public:
    std::vector<int> locateRightIntervals(std::vector<std::vector<int>>& ranges) {
        std::vector<std::pair<int, int>> indexedStarts;
        indexedStarts.reserve(ranges.size());

        for (int i = 0; i < ranges.size(); ++i) {
            indexedStarts.emplace_back(ranges[i][0], i);
        }

        std::sort(indexedStarts.begin(), indexedStarts.end());

        std::vector<int> output(ranges.size(), -1);

        for (int i = 0; i < ranges.size(); ++i) {
            int endVal = ranges[i][1];
            auto it = std::lower_bound(
                indexedStarts.begin(),
                indexedStarts.end(),
                std::make_pair(endVal, -1)
            );

            if (it != indexedStarts.end()) {
                output[i] = it->second;
            }
        }

        return output;
    }
};

Using std::make_pair(endVal, -1) as the search key works effectively because std::pair comparison evaluates the first element first. If start values are equal, the second element (-1) ensures the iterator points to the correct position without affecting the primary start-value comparision, given that original indices are non-negative.

Complexity Analysis

Both approaches share identical performance characteristics. Constructing the auxiliary array takes O(n) time. Sorting requires O(n log n). Each of the n intervals triggers a binary search operating in O(log n), resulting in a total time complexity of O(n log n). The auxiliary storage for start-index pairs and the result array consumes O(n) space. This efficiently handles the upper constraint limits while avoiding quadratic degradation.