如何高效计算给定区间与可平移区间列表的相交数量
2026-7-21
问题拆解与高效解法
先把你的需求拆成两种核心场景，对应不同的高效解法：
场景1：仅平移区间i，求最多能和多少个区间相交
假设区间i的长度是 len_i = r_i - l_i，当你把i平移到 (x, x+len_i) 时，它和区间j=(a_j, b_j)相交的条件是：x < b_j 且 x + len_i > a_j，说白了就是x得落在 (a_j - len_i, b_j) 这个范围内。每个j都对应这么一段x的有效区间，我们要找的就是x被多少个这样的区间覆盖，最大值就是平移i后能达到的最多相交数。
用扫描线算法实现（O(n log n) 时间）
- 先给每个j≠i生成两个事件点：
- 左端点：
(a_j - len_i, +1)—— 表示x进入这个范围时，相交数加1 - 右端点：
(b_j, -1)—— 表示x离开这个范围时，相交数减1
- 左端点：
- 把所有事件点排序：按坐标从小到大排，如果坐标一样，先处理
-1的事件（避免在端点处重复计数，比如x=b_j时，i的左端点刚好等于j的右端点，这时候两个区间不相交，所以得先减后加） - 扫描事件点算最大值：初始化当前相交数
current=0，最大数max_count=0，遍历排序后的事件点，每次更新current，同时记录最大的current值就行。
场景2：允许所有区间独立平移，求能和i相交的区间数
如果每个区间都能随便平移，那只要j不是空区间（也就是b_j > a_j），肯定能通过平移让它和i相交（比如直接把j挪到i的位置上）。这种情况答案就是L里所有非空区间的数量。
补充：你提到的普通无平移场景的排序方案
如果是不允许平移，直接算i原本和多少个区间相交，更高效的方法是：
- 提前把所有区间的右端点排序成数组
R_sorted，左端点排序成数组L_sorted - 用二分查找算不相交的数量：
- 右端点≤i左端点的区间数：
cnt_left = bisect_right(R_sorted, l_i) - 左端点≥i右端点的区间数：
cnt_right = len(L_sorted) - bisect_left(L_sorted, r_i)
- 右端点≤i左端点的区间数：
- 相交数量就是总区间数减去这两个数：
total = len(L) - cnt_left - cnt_right
这种方法预处理是O(n log n)，每次查询O(log n)，比扫描线更适合静态查询。
内容的提问来源于stack exchange，提问作者Daniel
相关产品推荐
相关产品推荐
