解题思路:书上那个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 人评分
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:859 |
不容易系列2 (C语言代码)浏览:589 |
多输入输出练习1 (C语言代码)浏览:1178 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:517 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1144 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:627 |
【蟠桃记】 (C语言代码)浏览:1021 |
用筛法求之N内的素数。 (C语言代码)浏览:664 |
青年歌手大奖赛_评委会打分 (C语言代码)浏览:2139 |
小O的数字 (C语言代码)浏览:1406 |