题目描述

AcWing 803s

样例

5
1 2
2 4
5 6
7 8
7 9

输出

3

思路:

将所有的区间按左端点从小到大排序,这样就可以将情况减少为3种.

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;

void merge(vector<PII> &segs)
{
    vector<PII> ans;//是存放最后存在的区间左右端点的容器,ans.size()就是最后的答案
    int st = -1e9-5,ed = -1e9-5;
    for(auto item : segs)
    {
        if(ed < item.first)//第三种情况,此时要将目前区间加入ans中,并更新新的区间
        {
            if(st != -1e9-5)//目前不是初始状态,即有区间存在.
            ans.push_back({st,ed});
            st = item.first,ed = item.second;
        }
        else ed = max(ed,item.second);//第一,二种情况
    }
    if(st != -1e9-5) ans.push_back({st,ed});
    segs = ans;
}

int main()
{
    vector<PII> segs;
    int n;
    scanf("%d",&n);
    int l,r;
    for(int i = 1;i <= n;i++)
    {
        scanf("%d %d",&l,&r);
        segs.push_back({l,r});
    }
    sort(segs.begin(),segs.end());
    merge(segs);
    printf("%d",segs.size());
    return 0;
}