贪心算法通过每步选择最早结束的活动来最大化不冲突活动数量，C++实现包括定义活动结构体、按结束时间排序并遍历选择兼容活动，时间复杂度O(n log n)，适用于满足贪心选择性质的问题。
贪心算法在C++中解决选择问题的核心是：每一步都做出当前最优的选择，希望最终结果是全局最优。针对“选择问题”，比如活动选择、区间调度等，贪心策略通常有效且实现简单。
活动选择问题描述
给定n个活动，每个活动有开始时间start和结束时间end，一个人在同一时间只能做一件事。目标是选出最多互不冲突的活动数量。贪心策略：按结束时间升序排序，优先选择最早结束的活动，这样可以为后续活动留出更多时间。
实现步骤
以下是C++中的具体实现方法：
1. 定义活动结构体，包含开始和结束时间 2. 按结束时间对活动排序 3. 遍历活动列表，选择与上一个选中活动不冲突的活动
C++代码示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
int start, end;
};
// 比较函数：按结束时间升序
bool compare(Activity a, Activity b) {
return a.end < b.end;
}
// 贪心选择活动
void selectActivities(vector<Activity>& activities) {
// 按结束时间排序
sort(activities.begin(), activities.end(), compare);
cout << "选中的活动：" << endl;
int i = 0;
cout << "[" << activities[i].start << ", " << activities[i].end << "]" << endl;
// 遍历剩余活动
for (int j = 1; j < activities.size(); j++) {
// 如果当前活动的开始时间大于等于上一个选中活动的结束时间
if (activities[j].start >= activities[i].end) {
cout << "[" << activities[j].start << ", " << activities[j].end << "]" << endl;
i = j; // 更新最后选中的活动
}
}
}
int main() {
vector<Activity> acts = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}};
selectActivities(acts);
return 0;
}
关键点说明
• 排序是贪心的前提：必须先按结束时间排序才能保证每次选择最优 • 冲突判断标准：当前活动的开始时间 ≥ 上一个选中活动的结束时间 • 时间复杂度：O(n log n)，主要消耗在排序上；选择过程是O(n)基本上就这些。只要问题满足贪心选择性质和最优子结构，这种实现方式高效且易于理解。注意不是所有选择问题都适用贪心，需要先验证正确性。
