贪心算法通过每步选择最早结束的活动来最大化不冲突活动数量，C++实现包括定义活动结构体、按结束时间排序并遍历选择兼容活动，时间复杂度O(n log n)，适用于满足贪心选择性质的问题。
贪心算法在C++中解决选择问题的核心是：每一步都做出当前最优的选择，希望最终结果是全局最优。针对“选择问题”，比如活动选择、区间调度等，贪心策略通常有效且实现简单。
活动选择问题描述
给定n个活动，每个活动有开始时间start和结束时间end，一个人在同一时间只能做一件事。目标是选出最多互不冲突的活动数量。贪心策略：按结束时间升序排序，优先选择最早结束的活动，这样可以为后续活动留出更多时间。
实现步骤
以下是C++中的具体实现方法：
1. 定义活动结构体，包含开始和结束时间 2. 按结束时间对活动排序 3. 遍历活动列表，选择与上一个选中活动不冲突的活动
C++代码示例
#include#include #include using namespace std; struct Activity { int start, end; }; // 比较函数：按结束时间升序 bool compare(Activity a, Activity b) { return a.end < b.end; } // 贪心选择活动 void selectActivities(vector & 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 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)基本上就这些。只要问题满足贪心选择性质和最优子结构，这种实现方式高效且易于理解。注意不是所有选择问题都适用贪心，需要先验证正确性。
