AcWing题解——803.区间合并

区间 A 和区间 B 有交集&＃xff0c;如图所示。

则有这样的数学关系&＃xff1a;

则有这样的数学关系&＃xff1a;

则有这样的数学关系&＃xff1a;

如上图所示&＃xff0c;我们可以很清晰的看到&＃xff0c;可以合并成 3 个区间&＃xff0c;如下图所示。

也就是 [1, 4]、[5, 6] 和 [7, 9] 这三个区间。

区间合并的过程图示可以参考我前面的一个题解&＃xff0c;https://blog.csdn.net/justidle/article/details/104553695。

数据范围分析

从题目中可以知道&＃xff0c;n 的最大值为 100000&＃xff0c;坐标范围是 [-10^9, 10^9]&＃xff0c;所以使用 int 表示足够。

对区间的描述&＃xff0c;可以使用 STL 的 pair&＃xff0c;也可以使用自定义的 struct。

1、读入所有数据并保存。

2、将所有区间进行排序。

3、遍历两个相邻区间&＃xff0c;看能否合并。如果可以合并&＃xff0c;则合并区间&＃xff0c;继续遍历直到最后一个区间。如果不可以合并&＃xff0c;区间数增加一&＃xff0c;继续合并以后的区间。

4、输出最终的区间数。

AC 参考代码

//https://www.acwing.com/problem/content/805/
//区间合并
#include
using namespace std;//区间定义
struct NODE {int x;int y;
};const int MAXN &＃61; 1e5&＃43;4;
NODE a[MAXN] &＃61; {};bool mycmp(const NODE &a, const NODE &b) {if (a.x!&＃61;b.x) {return a.x}int main() {int n;cin >> n;int i;for (i&＃61;0; i> a[i].x >> a[i].y;}//排序sort(a, a&＃43;n, mycmp);//遍历NODE curr &＃61; a[0];int ans &＃61; 1;for (i&＃61;1; i curr.y) {//没有交集ans&＃43;&＃43;;curr &＃61; a[i];} else {//包含或者相交关系curr.y &＃61; max(curr.y, a[i].y);}}cout <}