题意分析

题目背景

本题属于区间合并问题，要求将给定的一系列闭区间合并为互不相交的区间，并按升序输出。合并后的区间数目应最少，且输出顺序需满足区间起点严格递增。

核心问题

1. 输入：$n$个闭区间$[a_i, b_i]$，其中$1 \leq a_i \leq b_i \leq 10^6$。
2. 输出：合并后的互不相交区间，按起点升序排列。
3. 合并规则：若两个区间有重叠或相邻，则合并为一个新区间。

解题思路

1. 排序预处理

• 按起点排序：将所有区间按起点$a_i$升序排序，确保后续合并时只需线性扫描。$$\text{sort}([a_i, b_i]) \quad \text{by} \quad a_i$$

2. 线性扫描合并

1. 初始化：将第一个区间$[x, y]$作为当前合并区间。
2. 遍历区间：
   • 若当前区间$[a_i, b_i]$与$[x, y]$重叠或相邻（$a_i \leq y$），则更新$y$：$$y = \max(y, b_i)$$
   • 否则，输出$[x, y]$，并重置当前区间为$[a_i, b_i]$。
3. 终止处理：输出最后一个合并区间$[x, y]$。

3. 关键点

• 重叠判断：只需比较当前区间的起点与合并区间的终点。
• 时间复杂度：排序$O(n \log n)$，合并$O(n)$，总体$O(n \log n)$。

算法实现

代码框架

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Interval{
    int start;
    int stop;
};
 
bool operator < (const Interval &a, const Interval &b){
    return a.start < b.start;
}
 
int main(){
    int n;
    cin >> n;
    vector<Interval> in(n);
    for(int i = 0; i < n; ++i)
        cin >> in[i].start >> in[i].stop;
    sort(in.begin(), in.end());
    int x = in[0].start, y = in[0].stop;
    for(int i = 1; i < n; ++i){
        if(in[i].start >= x && in[i].start <= y){
           y = max(y, in[i].stop);
        }
        else{
            cout << x << " " << y << endl;
            x = in[i].start;
            y = in[i].stop;
        }
    }
    cout << x << " " << y << endl;
    return 0;

}

关键步骤

1. 输入与排序：读取区间数据并按起点排序。
2. 合并区间：
   • 初始化当前合并区间为第一个区间。
   • 遍历后续区间，动态更新合并区间的终点。
3. 输出结果：按升序输出所有合并后的区间。

复杂度分析

• 时间：$O(n \log n)$，主要由排序步骤决定。
• 空间：$O(n)$，存储输入区间。