题目:有n个区间,[ai, bi), 统计不相交区间最多有多少个?
贪心策略:将这n个区间按bi由小到大排序,然后从前向后遍历,每当遇到不相交的区间就加入目标集合,遍历完成后就找到了最多的不相交区间。
正确性证明:参见http://blog.csdn.net/dgq8211/article/details/7534488
以下是HDUOJ2037的源代码:
#include <iostream> #include <iomanip> #include <cmath> #define PI 3.1415927 using namespace std; struct Activity { int s, t; }; void bubbleSort(Activity *ac, int size) { for(int i=0; i<size-1; i++) { for(int j=0; j<size-1-i; j++) { if(ac[j].t>ac[j+1].t) { int tempS = ac[j].s; ac[j].s = ac[j+1].s; ac[j+1].s = tempS; int tempT = ac[j].t; ac[j].t = ac[j+1].t; ac[j+1].t = tempT; } } } } int main() { int n; while(cin>>n) { if(n==0) break; Activity *ac = new Activity[n]; for(int i=0; i<n; i++) { cin >> ac[i].s >> ac[i].t; } bubbleSort(ac, n); int count = 1;//第一个肯定要加进来 int t = ac[0].t;//维护不相交区间集合最大的t for(int i=1; i<n; i++) { if(ac[i].s>=t) { count++; t = ac[i].t; } } cout << count << endl; delete[]ac; } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)