找到每个给定的N个区间右侧最接近的非重叠区间的索引

题目解析

本文讨论如何找到每个给定的N个区间右侧最接近的非重叠区间的索引。给定的区间是指起始位置和结束位置已知的一段连续区间。非重叠区间指没有重叠的区间，即两个区间的交集为空。右侧最接近是指与当前区间结束位置最近的区间。

假设给定的N个区间按照起始位置升序排列，我们可以使用二分搜索查找右侧最接近的非重叠区间。可以将每个区间的结束位置看作一个数，然后对这些数进行二分搜索。

问题的难点

问题的难点在于如何表示非重叠区间。对于一个区间[a, b]，我们需要找到右侧最接近的非重叠区间，即右侧第一个区间的起始位置大于等于b。

我们可以使用一个数组endpoints来保存所有区间的结束位置，然后对这个数组进行排序。对于一个区间[a, b]，我们可以使用二分搜索找到右侧第一个大于等于b的位置。如果这个位置存在，则说明[a, b]的右侧有非重叠区间。否则，说明[a, b]的右侧没有非重叠区间。

C++代码实现

#include <vector>
#include <algorithm>
std::vector<int> find_right_non_overlapping_intervals(std::vector<std::pair<int, int>> intervals) {
    std::vector<int> endpoints(intervals.size());
    std::vector<int> result(intervals.size());
    for (int i = 0; i < intervals.size(); i++) {
        endpoints[i] = intervals[i].second;
    }
    std::sort(endpoints.begin(), endpoints.end());
    for (int i = 0; i < intervals.size(); i++) {
        int left = i + 1, right = intervals.size() - 1, index = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (intervals[mid].first <= intervals[i].second) {
                left = mid + 1;
            } else {
                index = mid;
                right = mid - 1;
            }
        }
        result[i] = index;
    }
    return result;
}

算法复杂度分析

经过排序之后，找到右侧最接近的非重叠区间的时间复杂度为O(logN)，因为是对每个区间都进行了二分搜索，所以总的时间复杂度为O(NlogN)。

空间复杂度为O(N)，因为需要使用一个数组保存所有区间的结束位置。