Skip to content

区间合并

把重叠的区间合成互不相交的区间,处理覆盖与日程类问题。

Updated View as Markdown

给你一堆区间,有的互相重叠。把它们整理成若干个互不相交的区间,这件事在日程安排、区间覆盖、时间统计里反复出现,做法固定,写熟就能直接套。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

考试 大纲要求 本章位置
NOI 入门级 1.4.3 基础算法:贪心法 为什么按左端点排序
CSP-J/S 第一轮 区间处理是常见的阅读程序题材 全章
CSP-J/S 入门级 4.3 基础算法:贪心的区间选点、区间覆盖问题 练习 2、练习 6
GESP C++ 六级 排序 + 贪心的综合应用(区间类问题的通用框架) 全章

问题

给定 n 个区间 [l_i, r_i],把所有有重叠的区间合并,输出合并后互不重叠的区间。

例如输入 [1,3] [2,6] [8,10] [9,12],合并后是 [1,6] [8,12]。

做法

  1. 按左端点从小到大排序。
  2. 维护一个当前合并区间 [curL, curR]。
  3. 依次看下一个区间:
    • 如果它的左端点不超过 curR,说明有重叠,把 curR 更新为两者右端点的较大值。
    • 否则没有重叠,输出当前区间,把当前区间换成新的这个。

按左端点排序之后,「会不会重叠」只需要看下一个区间的左端点和当前右端点的关系,一次扫描就能完成。

#include <bits/stdc++.h>
using namespace std;

struct Seg { int l, r; };

int main() {
    int n;
    cin >> n;
    vector<Seg> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;

    sort(a.begin(), a.end(), [](const Seg &x, const Seg &y) {
        return x.l < y.l;
    });

    vector<Seg> res;
    for (int i = 0; i < n; i++) {
        if (res.empty() || a[i].l > res.back().r) {
            res.push_back(a[i]);          // 不重叠,开一段新的
        } else {
            res.back().r = max(res.back().r, a[i].r); // 重叠,延长右端点
        }
    }

    for (auto &s : res) cout << s.l << " " << s.r << "\n";
    return 0;
}

为什么按左端点排序

如果按左端点排序,扫描到第 i 个区间时,它的左端点一定不小于之前所有区间的左端点。所以只要它的左端点和当前区间的右端点相接或重叠,就一定和当前这一段连得上,不需要回头去检查更早的区间。

换一个排序依据就会出错。按右端点排序时,一个右端点很大但左端点很小的区间可能排在后面,导致漏合并。

常见变体

变体 做法
数合并后还剩几个区间 合并后统计区间个数
求并集的总长度 每个合并区间的 r - l 相加(注意题目对区间长度的定义)
判断能否覆盖完整的一段 排序后维护「当前已覆盖到的最右位置」,看能否连续接上
插入一个新区间再合并 把新区间加入后重新排序合并
会议室安排 本质是求最大重叠次数,可以用排序或差分
并集覆盖多少个整数点 合并后每个区间累加 r - l + 1
最少几个点/箭覆盖全部区间 按右端点排序 + 贪心选点

覆盖判断这类题更接近贪心:按左端点排序,维护当前能连续覆盖到的最右端,只要下一个区间的左端点不大于「当前最右端加一」,就能继续往后接。面试里的「跳跃游戏」和「区间覆盖」都是这个思路。

示例:并集的总长度

题目描述

给定 n 个闭区间 [l_i, r_i],求它们并集覆盖的整数点个数。

输入格式

第一行一个整数 n;接下来 n 行,每行两个整数 l_i、r_i。

输出格式

输出一个整数,表示被覆盖的不同整数点个数。

数据范围

  • 1 \le n \le 10^5,|l_i|, |r_i| \le 10^9,l_i \le r_i。

输入输出样例

输入

3
1 5
3 8
10 12

输出

11

(并集是 [1,8] \cup [10,12],即 18 共 8 个点,加 1012 共 3 个点。)

题目分析

合并完之后,每个合并区间的贡献是 r - l + 1,全部加起来就是答案。

这里最容易错的是「+1」。闭区间 [1, 5] 包含 1、2、3、4、5 共 5 个整数点,而 r - l = 4,所以必须加 1。如果题目问的是「长度」而不是「点数」,那在某些定义下就是 r - l(连续线段长度),不加 1。

读题时先确认是「点数」还是「长度」——这是区间类题目最常见的失分点。本题明确说「整数点个数」,所以要 +1。

参考代码

注意这里合并的判断用的是 s.l > res.back().r,也就是 [1,3] 和 [4,6] 不合并(中间没有重叠,但也不缺整数点:3 和 4 相邻)。而如果题目要求「连续覆盖」,[1,3] 和 [4,6] 恰好能接上,因为下一个要盖的是位置 4,正好被 [4,6] 的左端点覆盖。「合并」和「连续覆盖」对「相邻」的处理不同,别混用。

示例:用最少的箭引爆气球

题目描述

在水平坐标轴上有 n 个气球,第 i 个气球的横向范围是 [l_i, r_i]。一支箭从某个坐标 x 竖直向上射出,能引爆所有满足 l_i \le x \le r_i 的气球。求最少需要几支箭才能引爆全部气球。

输入格式

第一行一个整数 n;接下来 n 行,每行两个整数 l_i、r_i。

输出格式

输出一个整数,表示最少需要的箭数。

数据范围

  • 1 \le n \le 10^5,|l_i|, |r_i| \le 10^9,l_i \le r_i。

输入输出样例

输入

4
10 16
2 8
1 6
7 12

输出

2

(在第 6 处射一箭可引爆 [2,8]、[1,6];在第 12 处射一箭可引爆 [10,16]、[7,12]。)

题目分析

这是区间合并思想的一个漂亮变体,也是**「按右端点排序」唯一最值得记住的场景**。

本章前面反复强调「按左端点排序」,但这道题必须按右端点排序,原因在于贪心策略不同:

  • 合并区间要问「哪些区间连成一片」,所以按左端点看「能不能接上」;
  • 选点引爆要问「一个点最多能覆盖几个区间」,所以按右端点看「一个点最远能管到哪里」。

贪心策略:按右端点从小到大排序,第一个箭射在第一个区间的右端点(这是能引爆它的最靠右的位置,也最有可能顺带引爆后面的)。然后跳过所有被这支箭覆盖的区间,对下一个没被覆盖的区间再射一支,以此类推。

为什么射在右端点最优? 假设当前必须有支箭引爆区间 i,那么射在 r_i 能覆盖「左端点 ≤ r_i」的所有区间;射在 r_i 左边覆盖得更少,射在 r_i 右边就漏掉了 i。所以 r_i 是局部最优,而这个局部最优不会影响后面的选择(越靠右越有利),贪心成立。

参考代码

这道题和「合并区间」的排序依据刚好相反,值得专门记住。判断依据一句话:问「连成一片」按左端点排,问「一个点能管多远」按右端点排。 这也是贪心题最容易混淆的地方——排序依据不是固定的,取决于你要维护的是什么。

用区间合并还是用差分

这两招经常出现在同一类题里,但解决的问题不一样:

要求的问题 用哪个
求多个区间的并集,或并集的总长度 区间合并
求每个位置被多少个区间覆盖 差分
求最多的重叠个数 差分,或者排序后扫描端点
判断能不能连续覆盖一整段 区间合并 + 贪心

简单记:只关心「被覆盖了没有」就用合并,关心「被覆盖了几次」就用差分。

复杂度

排序是 O(n \log n),扫描是 O(n),总复杂度 O(n \log n)。空间上只用了一个结果数组,O(n)。

常见易错点

  • 排序依据必须是左端点,写成右端点会出错。
  • 合并时右端点要取 max,不能直接覆盖。比如 [1,10] 后面接 [2,3],合并后仍是 [1,10]。
  • 判断是否重叠用 a[i].l <= res.back().r。区间端点相接时算不算重叠,要看题目定义,闭区间通常算重叠。
  • 数据量大时读入输出用 scanf / printf 或加快读,避免 I/O 拖慢。
  • 并集点数忘记 +1。闭区间 [1,5] 有 5 个整数点,r-l 只有 4。题目问「点数」还是「长度」要先看清楚。
  • 该按右端点排序的题按了左端点。合并区间按左端点,选点/射箭类按右端点,用错就得不到最优。
  • lastArrow 初值写 0。如果坐标可能是负数(如 -10^9),用 0 会让第一个区间被误判成「已被覆盖」。用 LLONG_MIN 或坐标下界减一更稳。
  • 用「当前区间变量」写法时,别漏掉最后一个区间。 上面的代码用 res 数组,每个区间都会被放进去;如果把写法改成用 curL、curR 两个变量维护当前区间,那循环结束后还要把最后一段单独输出一次。

练习

练习 1:合并区间

在线评测练习:P1522 合并区间

题目描述

给定 n 个闭区间,把它们之中有重叠的全部合并,输出合并后的区间个数,再按左端点从小到大输出每个区间。

若两个闭区间有公共点,则认为它们重叠、需要合并;端点恰好相接(例如 [1,3] 与 [3,5])也算重叠。

输入格式

第一行一个整数 n;接下来 n 行,每行两个整数 l、r。

输出格式

第一行输出合并后的区间个数 k;接下来 k 行,按左端点从小到大输出每个区间。

数据范围

  • 1 \le n \le 10^5
  • |l|, |r| \le 10^9
  • l \le r

输入输出样例

输入

4
1 3
2 6
8 10
9 12

输出

2
1 6
8 12

题目分析

这就是本章主代码的标准写法,正好可以拿来练手。核心是本章反复强调的两步:先按左端点排序,再一次扫描合并。

  • 排序:把所有区间按左端点从小到大排好。排完之后,扫描到第 i 个区间时,它的左端点一定不小于之前所有区间的左端点,所以「会不会重叠」只需看它和当前这一段右端点的关系,不必回头检查更早的区间。
  • 扫描合并:用结果数组 res 维护已经合并好的段,每次都拿最后一段去接新区间:
    • 若 s.l > res.back().r,说明接不上(注意闭区间端点相接算重叠,所以用严格的 >,等于时要合并),另起一段;
    • 否则接得上,把当前段右端点更新为 max(res.back().r, s.r)。

这里最容易写错的是右端要取 max,不能直接用新区间的右端覆盖。比如已有 [1,10],又来了 [2,3],合并后仍应是 [1,10];若直接赋成 3 就错了。

输出时先输出结果个数 res.size(),再按顺序逐行输出每个区间。总复杂度瓶颈在排序,O(n \log n),扫描是 O(n)。

参考代码

练习 2:连续覆盖

在线评测练习:P1445 区间覆盖

题目描述

给定目标区间 [0, L] 和 n 条线段,第 i 条线段的两端点为 l_i 和 r_i。请你选出最少的线段,使这些线段的并恰好覆盖整个区间 [0, L]。

如果无论怎么选都无法覆盖 [0, L],输出 -1。

输入格式

第一行两个整数 L 和 n,用一个空格隔开。

接下来 n 行,每行两个整数 l_i、r_i,用一个空格隔开,表示一条线段的两端。

输出格式

输出一行一个整数,表示最少需要的线段条数;无法覆盖时输出 -1。

数据范围

  • 1 \le L \le 10^9,1 \le n \le 10^4。
  • 0 \le l_i < r_i \le 10^9。

输入输出样例

输入

10 3
0 3
3 7
7 12

输出

3

题目分析

这是区间合并的「贪心版本」:不是求并集,而是求最少几段能连续地盖住 [0, L]。注意这里是连续覆盖——盖住的部分要首尾相连、不能有空隙,而不是只覆盖整数点。

做法沿用本章「按左端点排序 + 扫描」的框架:

  1. 把所有线段按左端点从小到大排序。
  2. 维护「当前已经连续覆盖到哪个位置」,记作 cur,从 0 开始(目标区间左端点是 0)。
  3. 在所有左端点不越过 cur 的线段里,挑右端点最大的那一个,把覆盖位置推到它的右端点。
  4. 如果某一步挑不出能继续往后接的线段(右端点都追不过 cur),说明中间有缺口,直接输出 -1。
  5. 当 cur 达到 L 时结束,输出所用线段条数。

为什么每次都挑右端点最大的?因为右端点越大,下一步可选的线段就越多,不会吃亏,这是贪心成立的直觉。

连续覆盖和「合并」对相邻的处理相同,但要小心别把「整数点覆盖」的写法套过来。 更新覆盖位置时应直接令 cur = best(当前已连续盖到 best),而不是 best + 1——如果写成 best + 1,相当于要求下一段从 best + 1 起头,会漏掉 (best, best+1) 这段,那是按整数点覆盖的思路,不是本题要求的连续覆盖。

参考代码

注意本题输入顺序是「先 L 后 n」,读入时别写反;覆盖目标的左端点是 0,所以 cur 从 0 出发,循环条件是 cur < L。

练习 3:最多同时在场的活动数

在线评测练习:P1512 区间最大覆盖次数

题目描述

数轴上有 n 个闭区间 [l_i, r_i],求被覆盖次数最多的位置被覆盖了多少次。

输入格式

第一行包含一个整数 n。

接下来 n 行,每行包含两个整数 l_i、r_i,中间用一个空格隔开,表示一个闭区间。

输出格式

输出一行一个整数,表示单个位置被覆盖的最大次数。

数据范围

  • 1 \le n \le 10^5。
  • 0 \le l_i \le r_i \le 10^9。

输入输出样例

输入

3
1 5
3 8
6 10

输出

2

输入

2
1 1
1 1

输出

2

位置 1 被两个区间各覆盖一次,共 2 次。

题目分析

求「最多重叠几个」用差分最直接:把每个区间看成「开始处 +1、结束处的下一个位置 -1」,把所有事件按坐标从小到大排序后扫描,维护当前重叠数,途中取最大值。

扫描时要把同一个坐标的所有事件一起处理。由于我们对每个区间记的是「l 处 +1、r + 1 处 -1」,闭区间的端点被正确覆盖到:结束的那次 -1 落在 r + 1,不会和「恰好在 r 开始的另一个区间」被误认为重叠。排序后 pair 默认先比坐标、再比增减量,-1 会排在 +1 前面,正好保证「先退场、再进场」,相接的两个区间不会被算成同时进行。

这正是本章「关心被覆盖了几次就用差分」的典型场景——只关心「覆盖了没有」才用合并,关心「覆盖了几次」就用差分。

参考代码

练习 4(进阶):插入一个区间

在线评测练习:P1523 插入区间

题目描述

给定一个已经按左端点排序、且互不重叠的区间列表,再给一个新区间 [L, R]。把新区间插进去,仍然保持「互不重叠、按左端点有序」,输出区间个数和每个区间。

若两个闭区间有公共点,则认为它们重叠、需要合并;端点恰好相接(例如 [1,3] 与 [3,5])也算重叠。

输入格式

第一行一个整数 n;接下来 n 行,每行两个整数表示一个已有区间;最后一行两个整数 L、R,表示待插入的区间。

输出格式

第一行输出插入后的区间个数 k;接下来 k 行,按左端点从小到大输出每个区间。

数据范围

  • 1 \le n \le 10^5
  • 坐标绝对值不超过 10^9
  • 已有区间互不重叠且按左端点升序给出,L \le R

输入输出样例

输入

3
1 3
6 9
12 15
2 7

输出

2
1 9
12 15

新区间 [2,7] 与前两个区间都有重叠,三者合并成 [1,9]。

题目分析

这是区间合并的变体,把「插入」化归成「排序 + 合并」即可。

最省事的写法:把新区间直接加进列表,重新排序后跑一遍本章标准的区间合并(按左端点排序后一次扫描,能接上就延长右端、取 max,接不上就另起一段)。复杂度 O(n \log n),对于 10^5 的数据完全够用。

如果要求 O(n),可以分三段处理:已有区间本就有序且互不重叠,先把整体在新区间左侧且不相交的区间原样输出,再把所有与新区间有交的区间(含端点相接)合并成一个,最后输出剩下的。不过分三段写很容易在边界上出错,平时做题先用排序合并的写法更稳——这也是本章「把插入这样的变体化归成排序 + 合并」的思路。

参考代码

练习 5:并集的总长度

在线评测练习:P1511 区间并集的整数点个数

题目描述

数轴上有 n 个闭区间 [l_i, r_i],求这些区间一共覆盖了多少个不同的整数点(被多个区间重复覆盖的点只算一次)。

输入格式

第一行包含一个整数 n。

接下来 n 行,每行包含两个整数 l_i、r_i,中间用一个空格隔开,表示一个闭区间。

输出格式

输出一行一个整数,表示被覆盖的不同整数点个数。

数据范围

  • 1 \le n \le 10^5。
  • |l_i| \le 10^9,l_i \le r_i。

输入输出样例

输入

3
1 5
3 8
10 12

输出

11

并集是 [1, 8] \cup [10, 12],1 到 8 共 8 个整数点,10 到 12 共 3 个,一共 11 个。

输入

2
-3 -1
0 0

输出

4

[-3,-1] 含 3 个整数点,[0,0] 含 1 个,没有重叠。

题目分析

就是正文「并集的总长度」那个示例的可提交版本。先用区间合并把重叠的段并成互不相交的若干段,再让合并后每个区间贡献 r - l + 1,累加即可。

两个必须想清楚的点:

  1. +1 不能漏。闭区间 [1,5] 有 5 个整数点,而 r - l 只有 4。题目问「整数点个数」,所以加 1;若问「长度」(连续线段长度),一般不加。
  2. 相邻但不重叠要不要合并? [1,3] 和 [4,6] 中间没有重叠,但也不缺整数点(3 和 4 相邻)。本题不需要合并也能算对:(3-1+1) + (6-4+1) = 3 + 3 = 6,与合并后 [1,6] 的 6 个点一致。所以合并判断用 s.l > res.back().r 就行。

另外注意坐标可能是负数(如样例 [-3,-1]),存放端点和答案都要用 long long,答案可能很大。

但如果题目要求的是「连续覆盖」(比如练习 2),相邻的 [1,3] 和 [4,6] 就算接上了,因为下一个要盖的位置 4 正好被覆盖。「合并」和「连续覆盖」对「相邻」的处理不同,这是本章最容易混的一处。

参考代码

练习 6(挑战):用最少的箭引爆气球

在线评测练习:P1521 最少箭引爆气球

题目描述

在水平坐标轴上有 n 个气球,第 i 个气球的横向范围是 [l_i, r_i]。一支箭从某个坐标 x 竖直向上射出,能引爆所有满足 l_i \le x \le r_i 的气球。求最少需要几支箭才能引爆全部气球。

输入格式

第一行一个整数 n;接下来 n 行,每行两个整数 l_i、r_i。

输出格式

输出一个整数,表示最少需要的箭数。

输入输出样例

输入

4
10 16
2 8
1 6
7 12

输出

2

数据范围

  • 1 \le n \le 10^5
  • |l_i|, |r_i| \le 10^9
  • l_i \le r_i

题目分析

这道题最关键的一点:排序依据和本章主线相反——要按右端点排序。

这是很值得警惕的地方。本章反复强调「按左端点排序」,但那是为了回答「哪些区间连成一片」。本题要回答的是「一个点最多能管多远」,所以要看右端点。

贪心策略:按右端点从小到大排序,箭射在当前区间的右端点 r。之后所有左端点 \le r 的区间都会被这支箭覆盖,直接跳过;遇到第一个左端点 > r 的区间,说明它没被覆盖,再射一支。

为什么射在右端点? 假设当前这个区间必须被某支箭引爆,射在 r_i 能覆盖「左端点 \le r_i」的全部区间;往左射覆盖得更少,往右射就漏掉了 i 自己。所以 r_i 是最优且不会伤害后续选择的位置。

和「合并区间」对照着记:

要回答的问题 排序依据 维护什么
哪些区间连成一片(合并) 左端点 当前合并段的右端
一个点最多能管多远(选点) 右端点 上一支箭的位置

排序依据不是固定的,取决于你要维护的是什么 ——这句话是整章最值得带走的经验。

参考代码

lastArrow 初值用 LLONG_MIN,保证第一个区间一定会触发「射一支箭」。如果你的坐标都是非负的,用 -1 也行——但用 LLONG_MIN 更通用,不会因为坐标范围变化而出错。

小结

区间合并的套路非常固定,记住一句话:按左端点排序,然后一次扫描,能接上就延长右端,接不上就另起一段。

  • 排序依据选左端点是正确性的关键,按右端点排序会漏合并。
  • 合并时右端点要取 max,不能用新区间的右端直接覆盖。
  • 只关心「被覆盖了没有」用合并,关心「被覆盖了几次」用差分。
  • 想要「最少几段盖住一整条线段」,在合并的基础上加贪心:每次在能接上的区间里挑右端最大的。
  • 总复杂度 O(n \log n),瓶颈在排序。

学完这一章,下面这些事应该能独立完成:

  • 写出区间合并的代码,并说清为什么排序依据必须是左端点。
  • 说清区间合并和差分的适用区别。
  • 写出「最少几段连续覆盖」的贪心代码,并说清为什么每次都挑右端点最大的。
  • 把「最多几个活动重叠」翻译成事件扫描或差分。
  • 把插入区间这样的变体化归成「排序 + 合并」。
  • 求并集覆盖的「整数点个数」时记得 r - l + 1,并分清「点数」与「长度」。
  • 用「按右端点排序 + 贪心射点」解决引爆气球这类「一个点管多远」的问题。
  • 根据要维护的东西选排序依据:问「连成一片」按左端点,问「一点管多远」按右端点。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close