题目描述
给定 N 个闭区间[ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N,表示区间数。
接下来 N 行,每行包含两个整数ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示所需的点的最小数量。
数据范围
1≤N≤10^5
,
−10^9≤ai≤bi≤10^9
输入样例:
3
-1 1
2 4
3 5
输出样例:
2
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=100010;
int n;
struct Range{
int l,r;
bool operator< (const Range &W)const{
return r<W.r;//确保按右端点排序
}
}range[N];
/*bool cmp(Range a,Range b) {//确保按右端点排序
return a.r < b.r;
}*/
int main(){
cin>>n;
for (int i=0;i<n;i++){
int l,r;
cin>>l>>r;
range[i]={l,r};
}
sort(range,range+n);
int res=0,ed=-2e9;
for(int i=0;i<n;i++){
if(range[i].l>ed){
res++;
ed=range[i].r;
}
}
cout<<res<<endl;
return 0;
}
python 代码
n=int(input())
arr=[list(map(int,input().split())) for i in range(n)]
arr.sort(key=lambda w:w[1]) #按右端点将区间从小到大排序
res=0
ed=-2e9
for i in range(n): #从前到后一次枚举每个区间
if(arr[i][0]>ed): #如果当前区间中已经包含该点直接pass,
#否则选择当前区间的右端点
res+=1
ed=arr[i][1]
print(res)