区间合并

题目

给定 \(n\) 个区间 \([l_i,r_i]\)，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：\([1,3]\) 和 \([2,6]\) 可以合并为一个区间 \([1,6]\)。

输入格式

第一行包含整数 \(n\)。

接下来 \(n\) 行，每行包含两个整数 \(l\) 和 \(r\)。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

\(1≤n≤100000\)，
\(−10^9≤l_i≤r_i≤10^9\)

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

思路

1. 将所有区间用pair存储

2. 之后对这个数组进行排序，确保位于前面的区间的左边界始终小于后面区间的左边界

3. 取出数组中第一个区间进行维护，记为\(temp\)

4. 遍历整个区间数组, 令count = 0；

5. 当前的区间（第i个区间），\(i.first > temp.second\) 则 \(temp = i， count ++\)

   若 \(i.first <= temp.first\) $$ \(item.first <= temp.second\) 则 \(temp.second = i.second;\)

6. 最终合并后，有 \(count + 1\) 个区间

代码

# include<iostream>
# include<algorithm>
# include<vector>

using namespace std;

const int N = 1e5 + 10;
typedef pair<int, int> PII;

vector<PII> all;


int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) {
        int a, b;
        cin >> a >> b;
        all.push_back({a, b});
    }
    
    sort(all.begin(), all.end());
    
    PII temp = all.front();
   
    int count = 0;
    for(auto item : all) {
        if(temp.second < item.first) {
            temp = item;
            count ++;
            continue;
        }
    
        
        if(temp.second < item.second && item.first <= temp.second){
            temp.second = item.second;
        }
    }
    
    cout << count + 1;
    return 0;
}