题解 | 活动安排

解题思路

贪心策略选择，按照活动结束时间排序，每次选择结束时间最早的活动，这样可以为后面的活动留出更多时间空间。具体步骤

1. 读入所有活动的开始时间和结束时间
1. 按照结束时间从小到大排序
1. 选择第一个活动（结束时间最早的）
1. 遍历剩余活动：
- 如果当前活动的开始时间 $≥$ 上一个选中活动的结束时间
- 则选择该活动，更新最后活动的结束时间
1. 输出选中的活动数量

代码

cpp
java
python

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

int main() {
    int n;
    cin >> n;
    
    // 存储活动的开始时间和结束时间
    vector<pair<int, int>> activities(n);
    for(int i = 0; i < n; i++) {
        cin >> activities[i].second >> activities[i].first;  // 注意这里交换了顺序
    }
    
    // 按照结束时间排序
    sort(activities.begin(), activities.end());
    
    int count = 1;  // 至少可以选择一个活动
    int lastEnd = activities[0].first;  // 记录上一个选择的活动的结束时间
    
    // 遍历所有活动
    for(int i = 1; i < n; i++) {
        if(activities[i].second >= lastEnd) {  // 如果当前活动的开始时间大于等于上一个活动的结束时间
            count++;
            lastEnd = activities[i].first;
        }
    }
    
    cout << count << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 存储活动的开始时间和结束时间
        int[][] activities = new int[n][2];
        for(int i = 0; i < n; i++) {
            activities[i][1] = sc.nextInt();  // 开始时间
            activities[i][0] = sc.nextInt();  // 结束时间
        }
        
        // 按照结束时间排序
        Arrays.sort(activities, (a, b) -> a[0] - b[0]);
        
        int count = 1;  // 至少可以选择一个活动
        int lastEnd = activities[0][0];  // 记录上一个选择的活动的结束时间
        
        // 遍历所有活动
        for(int i = 1; i < n; i++) {
            if(activities[i][1] >= lastEnd) {  // 如果当前活动的开始时间大于等于上一个活动的结束时间
                count++;
                lastEnd = activities[i][0];
            }
        }
        
        System.out.println(count);
    }
}

n = int(input())
activities = []

# 读入活动时间
for i in range(n):
    start, end = map(int, input().split())
    activities.append((end, start))  # 注意这里交换了顺序

# 按照结束时间排序
activities.sort()

count = 1  # 至少可以选择一个活动
last_end = activities[0][0]  # 记录上一个选择的活动的结束时间

# 遍历所有活动
for i in range(1, n):
    if activities[i][1] >= last_end:  # 如果当前活动的开始时间大于等于上一个活动的结束时间
        count += 1
        last_end = activities[i][0]

print(count)

算法及复杂度分析

算法：贪心

时间复杂度：
- 排序： $\mathcal{O}(nlogn)$
- 遍历选择活动： $\mathcal{O}(n)$
- 总时间复杂度： $\mathcal{O}(nlogn)$
空间复杂度：
- $\mathcal{O}(n)$ ，用于存储活动信息
正确性证明：
- 选择结束时间最早的活动可以为后面留出最多的时间
- 这样可以安排最多的活动
注意事项：
- 输入数据范围较大，注意使用合适的数据类型
- 排序时需要同时考虑开始时间和结束时间
- 活动时间为左闭右开区间 $[a_i,b_i)$