一本通-1236：区间合并（区间贪心）

【题目描述】 给定 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

---

#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int start, end;

    bool operator<(const Node & obj) const
    {
        return (start < obj.start) || (start == obj.start && end < obj.end);
    }
};

int n;
vector<Node> seq(50005);

void solve()
{
    int start = seq[0].start, end = seq[0].end;
    for (int i = 1; i < n; ++i) {
        if (seq[i].start > end) {
            cout << "no" << endl;
            return;
        }
        else end = max(end, seq[i].end);
    }

    cout << start << ' ' << end << endl;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> seq[i].start >> seq[i].end;
    sort(seq.begin(), seq.begin() + n);

    solve();

    return 0;
}