【题目描述】

给定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;  }