【每周三道题】【题解】普及题：区间合并

每周三道题

『每周三道题』是计蒜客信息学推出的周更栏目。每周，在我们都会在公众号上都会发布由简到难，共三道信息学题目，并于次日公布题解。欢迎各位同学积极踊跃地参与解题哟！

题解

可以对区间按左端点从小到大排序，左端点相同按右端点从小到大排序，记下来当前遇到的最右边的点 r ，刚开始是最左边区间的右端点，然后依次看每个区间，如果这个区间的左端点比 r 大，那中间就有空的区域了，就达不到题目要求了，否则就可以接着连上去，不过如果这个区间的右端点比 r 大，那么现在遇到的最右边的点就是这个区间的右端点了，就把 r 更新成这个区间的右端点。

标程

#include <iostream>#include <algorithm>using namespace std;struct node { int a; int b;};bool cmp(node x, node y) { // 比较函数 if (x.a != y.a) { return x.a < y.a; } return x.b < y.b;}node p[50005];int main() { int n, r; bool f; cin >> n; for (int i = 0; i < n; i++) { cin >> p[i].a >> p[i].b; } sort(p, p + n, cmp); // 排序 r = p[0].b; f = true; for (int i = 1; i < n; i++) { if (p[i].a > r) { // 中间有空的区域了 f = false; break; } if (p[i].b > r) { // 更新目前遇到的最右边的点 r = p[i].b; } } if (f) { cout << p[0].a << ' ' << r << endl; // 输出答案 } else { cout << 'no' << endl; } return 0;}