用贪心算法解决活动安排问题

活动安排问题是一种经典的贪心算法问题，它要求在一系列争用某一公共资源的活动中，选择最大的相容活动子集合。具体来说，给定n个活动，每个活动都有一个开始时间和结束时间，同一时间只能进行一个活动，问最多能安排多少个活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能够被安排。具体算法思路如下：
1.将所有活动按照结束时间递增排序。
2.选择开始时间尽可能早的活动。
3.每次选择活动的开始时间必须大于上一个活动的结束时间。

这个算法的正确性可以通过反证法证明。假设在最优解中，选择的第一个活动不是结束时间最早的活动，那么我们可以将这个活动替换成结束时间最早的活动，这样就可以安排更多的活动。因此，我们可以得出结论：选择结束时间最早的活动是最优解的一部分。

下面是一个C++实现的例子，供你参考：

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

struct Activity {
    int num, start, end, mark;
};

bool comp(Activity a, Activity b) {
    return a.end < b.end;
}

void Select(Activity act[], int n) {
    int begin = act[1].start;
    for (int i = 1; i <= n; i++) {
        if (act[i].start >= begin) {
            begin = act[i].end;
            act[i].mark = 1;        }
    }
}

int main() {
    Activity act[101];
    int n;
    while (cin >> n && n != 0) {
        for (int i = 1; i <= n; i++) {
            cin >> act[i].start >> act[i].end;
            act[i].num = i;
            act[i].mark = 0;
        }
        sort(act + 1, act + n + 1, comp);
        Select(act, n);
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (act[i].mark == 1) {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}