区间贪心策略，杭电2073题之NOAC

问题：给出多个电视节目的时间段，问如何安排时间可以看到完整的最多的节目。算法思路1：对所有节目开始时间由晚到早排序后，从头开始选取节目并且下一个节目的结束时间<上一个节目的开始时间。每次选取最晚开始时间的节目相当于这个节目之前的时间更多。算法思路2：其实和1的想法一样。这次我们每次选取节目结束时间最早的节目，这样相当于看完这个节目后剩余的时间更多。代码采用算法思路1

#include
#include 
using namespace std;struct Program
{int start;int end;
};
bool cmp(const Program &a, const Program &b)
{if (a.start == b.start){return a.end < b.end;}else{return a.start > b.start;}
}
int main()
{int n;while (cin >> n) {if (n == 0) break;Program programs[100];for (int i = 0; i < n; i++) {cin >> programs[i].start >> programs[i].end;}sort(programs, programs + n, cmp);int count = 1;int start = programs[0].start;for (int i = 1; i < n; i++){if (programs[i].end <= start){start = programs[i].start;count++;}}cout << count << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！