活动选择
进阶活动选择是贪心策略最经典的入门案例，按结束时间排序即可。
// 算法讲解
活动选择
输入偶数个整数，每对代表一个活动的起止时间。
待机
速度 中
待机 ⌨1int activitySelect(vector<pair<int,int>>& act) {
2 sort(act.begin(), act.end(),
3 [](auto& a, auto& b) { return a.second < b.second; });
4 int count = 1, lastEnd = act[0].second;
5 for (int i = 1; i < (int)act.size(); i++) {
6 if (act[i].first >= lastEnd) {
7 count++;
8 lastEnd = act[i].second;
9 }
10 }
11 return count;
12}
复杂度分析
时间 O(n log n)
空间 O(n)
最优 O(n) 已排序时
最坏 O(n log n)
算法讲解
活动选择问题给出若干带起止时间的活动，目标是选出尽可能多的互不重叠的活动。
贪心策略是按结束时间排序后，每次都选最早结束且与已选活动不冲突的活动。
直观上理解：越早结束的活动，给后续活动留的余地越大，因此"先拿走最容易满足的"就是最优策略。
正确性通常用交换论证证明：任何最优解都可以通过替换为贪心选择而不减少活动数。