活动安排问题贪心算法c

活动安排问题是典型的贪心算法问题，也被称为区间调度问题。假设有n个活动，每个活动有一个开始时间s和结束时间f。如果两个活动的时间段不重叠，则它们可以安排在同一时间段内，求最多可以安排多少个活动？

一种贪心策略是按照结束时间从早到晚排序，然后依次选取结束时间最早且不与已选中的活动时间重叠的活动。这种策略的正确性可以用反证法证明：假设最优解中某个活动A与贪心策略得到的活动集合S中的某个活动B时间重叠，那么将B换成A，得到的活动集合S'的大小不小于原来的S，与假设矛盾，因此贪心策略是正确的。

以下是C++实现：

#include <iostream>
#include <algorithm>
using namespace std;

struct Activity {
    int start, end;
    bool operator < (const Activity& a) const {
        return end < a.end;
    }
}act[100];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> act[i].start >> act[i].end;
    }
    sort(act, act + n); //按结束时间从早到晚排序
    int cnt = 0, lastEnd = 0;
    for (int i = 0; i < n; ++i) {
        if (act[i].start >= lastEnd) {
            ++cnt;
            lastEnd = act[i].end;
        }
    }
    cout << cnt << endl;
    return 0;
}

时间复杂度为O(nlogn)，其中n为活动数目。