【正经题解】Gold King安排计划

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

// 活动时间结构体
struct Activity {
    int begin, end;
} activities[10005];

// 比较函数，用于排序
bool compare(Activity a1, Activity a2) {
    if (a1.end != a2.end)
        return a1.end < a2.end;
    if (a1.begin != a2.begin)
        return a1.begin < a2.begin;
}

// 快速读取整数
int readInt() {
    int x = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}

int main() {
    int testCases, activitiesCount, endTime;
    // 读取测试数据组数
    cin >> testCases;

    while (testCases--) {
        // 读取每组测试数据
        activitiesCount = readInt();
        for (int i = 0; i < activitiesCount; i++) {
            // 读取活动的开始和结束时间
            activities[i].begin = readInt();
            activities[i].end = readInt();
        }

        // 按结束时间升序排序
        sort(activities, activities + activitiesCount, compare);

        // 贪心算法选择最多能安排的活动数量
        endTime = activities[0].end;
        int count = 1;
        for (int i = 1; i < activitiesCount; i++) {
            if (activities[i].begin > endTime) {
                count++;
                endTime = activities[i].end;
            }
        }

        // 输出结果
        printf("%d\n", count);
    }

    return 0;
}