抄袭党请跳到最后

题目描述

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入样例:

3
-1 1
2 4
3 5

输出样例:

2

思路

1.将每个区间按右端点排序
2.开for枚举每个区间
（1） 若上次点的一个点包含在这个区间里，continue;
（2） else? 点一下这个区间的右端点

c++代码

#include<bits/stdc++.h>//万古不变万能头
using namespace std;
#define PII pair<int,int>//偷懒技巧
int n,t1,t2,t,s;
PII a[100005];//定义
int cmp(PII a,PII b)
{
    return a.second<b.second;
}//为了后来的sort
int main(){//main
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&t1,&t2);
        a[i]={t1,t2};
    }//输入
    sort(a,a+n,cmp);//将每个区间按右端点排序
    for(int i=0;i<n;i++)
    {
        if(i==0) s++,t=a[0].second;//没用的代码
        if(a[i].first<=t) continue;//若上次点的一个点包含在这个区间里，continue;
        else s++,t=a[i].second;//else? 点一下这个区间的右端点
    }//核心
    cout<<s;//输出
    return 0;//万古不变的return 0;
    while(1)//反抄袭
}