貪心
1、確定候選集： 將同一節目的開始時間與結束時間以結構體的方式存儲。 2、貪心策略： 對候選集進行預處理：對所有節目的結束時間由小到大進行排序處理。 遍歷一遍排好序的數組：首先將數組第一個位置的節目加入到解集中，且記錄此節目的結束時間，再依次向后找當滿足當前節目的開始時間比之前剛加入到解集中的節目的結束時間大或者相等時，將當前節目加入解集中，并記錄當前節目的結束時間，否則跳過當前節目向后尋找，直到遍歷完數組所有元素，解集中的節目數既是答案。 3、證明：當選擇的當前節目的結束時間越小時，剩余時間越多，則越能安排更多的節目（更嚴謹的證明可以使用數學歸納法與反證法）。
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;struct activity{ int acBegin; int acEnd;};int n;int ans;bool ifStart;activity ac[105];bool cmp(const activity left, const activity right) { return left.acEnd < right.acEnd;}int main() { while (~scanf("%d", &n)) { if (n == 0) break; ans = 0; ifStart = false; for (int i = 0; i < n; ++i) { scanf("%d%d", &ac[i].acBegin, &ac[i].acEnd); } sort(ac, ac + n, cmp); int lastEnd; for (int i = 0; i < n; ++i) { if (!ifStart) { ifStart = true; ans++; lastEnd = ac[i].acEnd; } else { if (ac[i].acBegin >= lastEnd) { ans++; lastEnd = ac[i].acEnd; } } }新聞熱點
疑難解答
