解题思路:
贪心区间
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语言代码)浏览:481 |
C语言训练-委派任务* (C语言代码)..................竟然是第一个浏览:2175 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:458 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:661 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:372 |
1157题解浏览:711 |
简单的a+b (C语言代码)浏览:543 |
判定字符位置 (C语言代码)浏览:792 |
C语言训练-自守数问题 (C语言代码)浏览:740 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:673 |