【题目描述】

给定n个闭区间[ai,bi]，其中i=1,2,...n。任意两个相邻或相交或相邻的闭区间可以合并为一个闭区间。例如，[1,2]和[2,3]可以合并为[1,3]。

[1,3]和[2,4]可以合并为[1,4]，但是[1,2]和[3,4]不可以合并。

我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，则将这个闭区间输出，否则输出no

【输入描述】

第一行为一个整数n，3<n<50000。表示输入区间的数量。

之后n行，在第i行上（1<=i<=n）,为两个整数ai和bi，整数之间用一个空格分隔，表示区间[ai,bi] 

(其中1<=ai<=bi<=10000)

【输出描述】

输出一行，如果这些区间最终可以合并为一个闭区间，输出这些闭区间的左右边界，用单个空格隔开；否则输出no

【样例输入】

5
5 6
1 5
10 10
6 9
8 10

【样例输出】

1 10

【题目分析】

排序区间：首先将所有区间按照左端点从小到大排序。按顺序合并区间。

贪心合并：

初始化 merged_interval 为第一个区间。

遍历后续区间，如果当前区间与 merged相交或相邻，则更新 merged 的右端点为两者的最大值。

如果不能合并，则直接返回 no。

检查是否合并完成：如果最终 merged 包含了所有区间，则输出它；否则输出 no。

【参考答案】

#include <bits/stdc++.h>
using namespace std;
// 定义区间结构体
struct Interval {
    int start;
    int end;
};
Interval a[100000];
bool cmp(Interval a,Interval b){
	return a.start<b.start;
}

int main() {
    int n;
    cin >> n;
    // 输入区间
    for (int i = 0; i < n; i++) {
        cin >> a[i].start >> a[i].end;
    }
    sort(a, a+n,cmp);
    // 初始化合并区间
    Interval merged = a[0];
    bool canMergeAll = true;
    // 尝试合并
    for (int i = 1; i < n; i++) {
        if (a[i].start <= merged.end) {
            // 更新右端点
            if (a[i].end > merged.end) {
                merged.end = a[i].end;
            }
        } else {
            canMergeAll = false;
            break;
        }
    }

    // 输出结果
    if (canMergeAll) {
        cout << merged.start << " " << merged.end << endl;
    } else {
        cout << "no" << endl;
    }

    return 0;
}