寻找有序区间集合中首个相交区间的O(N)更优算法

当然可以实现优于O(N)的高效算法，核心思路是利用原区间按起始元素升序排列的特性，结合预处理的单调数组，通过两次二分查找完成查询，时间复杂度为O(logN)。

前置分析 #

两个区间[s1,e1]和[q_s,q_e]相交的充要条件是：s1 ≤ q_e 且 e1 ≥ q_s。

由于原区间按s1升序排列，不相交的区间可分为两类：

1. 完全在查询区间左侧：e1 < q_s（这类区间的s1必然≤后续区间的s1，但e1太小，无法覆盖查询区间起点）
2. 完全在查询区间右侧：s1 > q_e（这类区间是连续的一段，从某个位置开始往后）

我们要找的是第一个不在这两类中的区间，也就是第一个满足s1 ≤ q_e 且 e1 ≥ q_s的区间。

关键预处理：构建单调不减的max_end数组 #

预先计算一个max_end数组，其中max_end[i]表示从第0个到第i个区间的end值的最大值。由于每次取前序最大值，这个数组是单调非递减的，这是实现二分查找的核心基础。

以你的示例集合为例：
原区间：{1,3}, {1,2}, {2,4}, {2,2}, {2,3}, {3,5}, {3,3}, {3,7}
max_end数组：[3, 3, 4, 4, 4, 5, 5, 7]

查询步骤（两次二分查找） #

步骤1：确定候选区间的右边界 #

用upper_bound找到第一个start > q_e的区间位置，记为right_idx。这意味着[0, right_idx-1]范围内的所有区间start ≤ q_e，有可能与查询区间相交；而[right_idx, end)的区间完全在右侧，直接排除。

如果right_idx == 0，说明所有区间都在查询区间右侧，直接返回end()。

步骤2：定位第一个相交的区间 #

在max_end[0..right_idx-1]范围内，用二分查找找到第一个值≥q_s的位置target_idx：

• 如果找不到这样的位置（即max_end[right_idx-1] < q_s），说明候选区间的end都小于q_s，完全在左侧，返回end()。
• 否则，target_idx就是第一个相交区间的索引：
  • 因为max_end单调不减，target_idx之前的所有max_end值都< q_s，说明这些区间的end都< q_s，完全在左侧，不相交。
  • 而max_end[target_idx] ≥ q_s，结合max_end的定义，必然是第target_idx个区间的end ≥ q_s，同时它的start ≤ q_e（处于候选范围内），满足相交条件。

代码实现（C++为例） #

预处理代码 #

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

struct Interval {
    int start;
    int end;
    Interval(int s = 0, int e = 0) : start(s), end(e) {}
};

vector<int> preprocess_max_end(const vector<Interval>& intervals) {
    vector<int> max_end;
    int current_max = -1;
    for (const auto& interval : intervals) {
        current_max = max(current_max, interval.end);
        max_end.push_back(current_max);
    }
    return max_end;
}

查询函数 #

vector<Interval>::iterator find_first_overlap(const vector<Interval>& intervals, const vector<int>& max_end, const Interval& query) {
    int q_s = query.start;
    int q_e = query.end;

    // 步骤1：找第一个start > q_e的区间
    auto it_right = upper_bound(intervals.begin(), intervals.end(), q_e,
        [](int val, const Interval& interval) {
            return val < interval.start;
        });
    int right_idx = it_right - intervals.begin();
    if (right_idx == 0) {
        return intervals.end();
    }

    // 步骤2：在max_end[0..right_idx-1]中找第一个≥q_s的位置
    int left = 0;
    int right = right_idx - 1;
    int target_idx = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 避免溢出
        if (max_end[mid] >= q_s) {
            target_idx = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    if (target_idx == -1) {
        return intervals.end();
    }

    return intervals.begin() + target_idx;
}

验证示例查询 #

用你的测试用例验证：

• 查询{0,0}：right_idx=0 → 返回end()
• 查询{2,4}：right_idx=8，找到target_idx=0 → 返回第0个区间
• 查询{3,8}：right_idx=8，找到target_idx=0 → 返回第0个区间
• 查询{4,9}：right_idx=8，找到target_idx=2 → 返回第2个区间
• 查询{7,8}：right_idx=8，找到target_idx=7 → 返回第7个区间
• 查询{8,9}：target_idx=-1 → 返回end()

完全匹配预期结果。

优势说明 #

• 预处理仅需O(N)时间，之后每次查询都是O(logN)，适合多次查询的场景。
• 避免了线性扫描的低效，当区间数量很大时，性能提升非常明显。

内容的提问来源于stack exchange，提问作者Robinson