区间合并

区间合并主要需要考虑三种情况

• 两个区间没有交集
• 两个区间有交集

思路

我们可以使用st和ed用来控制每一次最大区间的左右端点

根据贪心的策略，我们可以先通过left的值进行排序

考虑多种情况，如果发现上一次的ed比这一次的st小的话，说明这是一种全新的区间

否则的话，合并两个区间ed取两个右端点的最大值

#include <bits/stdc++.h>
using namespace std;
const int N = 2e9;
typedef pair<int,int> PII;
vector<PII> v,ans;
int a,b;
int main(){
    int n;
    cin >> n;
    while(n--) {
        cin >> a >> b;
        v.push_back({a,b});
    }

    sort(v.begin(),v.end());
    int st = -2e9, ed = -2e9;
    for(auto item : v) {
        if(ed < item.first) {
            if(st != -2e9) ans.push_back({st,ed});
            st = item.first;ed = item.second;
        }else {
            ed = max(ed,item.second);
        }

    }

    if(st != -2e9) ans.push_back({st,ed});


    cout << ans.size() << endl;

    return 0;
}