3 条题解

  • 0
    @ 2025-12-14 12:02:52
    #include <bits/stdc++.h>
    using namespace std;
    
    // 定义区间结构体,left=左端点,right=右端点,命名更清晰
    struct Interval {
        int left;
        int right;
    } a[50005]; // n最大50000,数组开50005足够
    
    // 排序规则:按左端点升序排列(核心修正点)
    bool cmp(Interval x, Interval y) {
        return x.left < y.left;
    }
    
    int main() {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i].left >> a[i].right;
        }
    
        // 对区间按左端点排序(核心修正点)
        sort(a, a + n, cmp);
    
        // 初始化合并后的区间为第一个区间
        int merge_left = a[0].left;
        int merge_right = a[0].right;
    
        // 从第二个区间开始遍历合并(核心修正点)
        for (int i = 1; i < n; i++) {
            // 当前区间能和已合并区间相交/相邻,合并
            if (a[i].left <= merge_right) {
                // 右端点取最大值(核心修正点,避免缩小)
                merge_right = max(merge_right, a[i].right);
            } else {
                // 无法合并成一个区间,输出nono
                cout << "no" << endl;
                return 0;
            }
        }
    
        // 所有区间合并完成,输出最终区间
        cout << merge_left << " " << merge_right << endl;
        return 0;
    }
    

    信息

    ID
    371
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    30
    已通过
    4
    上传者