解题思路

n 个活动要用礼堂，每个有开始和结束时间。同一时间礼堂只能被一个活动使用。求最多能安排几个活动。

思路：贪心 — 按结束时间排序，每次选最早结束的。

1. 把所有活动按结束时间从早到晚排序
2. 选第一个活动（结束最早）
3. 之后每次选开始时间不早于已选活动结束时间的活动
4. 重复直到选完

为什么要选最早结束的？ 因为结束越早，留给后面活动的时间越多，能安排的活动就越多。

举例：有 11 个活动

• 按结束时间排序后，依次选结束最早且与已选不冲突的
• 最多可选 4 个活动

参考代码

#include <iostream>
using namespace std;

int n, a[110], b[110];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];

    // 按结束时间排序
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= n - i; j++) {
            if (b[j] > b[j + 1]) {
                swap(a[j], a[j + 1]);
                swap(b[j], b[j + 1]);
            }
        }
    }

    int end = b[1];  // 已选活动的结束时间
    int cnt = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] >= end) {  // 不冲突
            cnt++;
            end = b[i];
        }
    }

    cout << cnt;
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，排序
• 空间复杂度：O(N)