解题思路:
贪心区间
1.对区间左端点进行从大到小排序,左端点相同则按右端点从小到大排序;
2.记录排列好的第一个被选中区间的左端点,如果下一个区间的右端点小于他,就选择;
注意事项:
要选中第一个元素,然后再比较
参考代码:
#include<bits/stdc++.h> using namespace std; struct intver{ int x,y; //开区间左右端点 }I[1005]; int cmp(intver a,intver b) { if(a.x!=b.x) return a.x>b.x; //先按左端点从大到小排列 else return a.y<a.y; } int main() { int n; cin>>n; for(int i=0;i<n;i++) { scanf("%d%d",&I[i].x,&I[i].y); } sort(I,I+n,cmp); int ans=1,lastx=I[0].x; //ans记录不相交的区间个数,lastx记录上一个被选中区间的左端点,ans=1表示选了按照我的排列规则选了第一个 for(int i=1;i<n;i++) { if(I[i].y<=lastx)//如果该区间右端点在lastx的左边,表示不相交,要选 { lastx=I[i].x; //以I[i]作为新的选中区间 ans++; //记录选择中的区间 } } cout<<ans; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题9.2 (Java代码)浏览:626 |
十->二进制转换 (C语言代码)浏览:1291 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:511 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:600 |
【亲和数】 (C语言代码)浏览:503 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:472 |
幸运数 (C++代码)浏览:1264 |
大家好,我是验题君浏览:577 |
杨辉三角 (C语言代码)浏览:484 |
链表数据求和操作 (C语言代码)浏览:950 |