解题思路:书上那个4.4.2已经很细了,期末时要是忘记了就去翻122页,多覆盖效率高
注意事项:题中为开区间
参考代码:
#include<bits/stdc++.h>
using namespace std;
typedef struct interval
{
int x,y;//区间两端
} Interval;
Interval arr[1010];//题目要求
int cmp(Interval a,Interval b)
{
if(a.x!=b.x ) return a.x>b.x;//按左端点从大到小排序。当两区间比较,有端点相等时 选区间大的
else return a.y<b.y; //左端点相同时按右端点从小到大排序
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>arr[i].x>>arr[i].y;
sort(arr,arr+n,cmp);//把区间从小到大排序
int ans=1;//ans记录不相交区间个数
int lastX=arr[0].x;//lastX记录上一个被选中区间的左端点
for(int i=1;i<n;i++)
{
if(arr[i].y<=lastX)//当右端点小于上个被选中区间的左端点时
{
ans++;// 不相交区间个数加一
lastX=arr[i].x;//上个被选中区间更新
}
}
cout<<ans<<endl;
return 0;
}
0.0分
0 人评分