解题思路:
贪心区间
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语言代码)浏览:1427 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:468 |
最小公倍数 (C语言代码)浏览:1025 |
1012题解浏览:861 |
简单的a+b (C语言代码)浏览:414 |
输入输出格式练习 (C语言代码)浏览:743 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:455 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:549 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:713 |
简单的a+b (C语言代码)浏览:645 |