活动安排贪心算法c++

活动安排问题是一个经典的贪心算法应用。在这个问题中，我们有一组活动，每个活动有一个开始时间和结束时间。我们的目标是选择最多的不重叠活动，即使可能的话，使得它们尽可能地多。

下面是一个使用贪心算法解决活动安排问题的C++代码示例：

#include <iostream>
#include <vector>
#include <algorithm>

// 活动结构体
struct Activity {
    int start;
    int end;
};

// 比较函数，按照结束时间递增排序
bool compare(Activity a, Activity b) {
    return a.end < b.end;
}

// 活动安排函数
void activitySelection(std::vector<Activity>& activities) {
    // 按照结束时间递增排序
    std::sort(activities.begin(), activities.end(), compare);
    
    // 第一个活动总是被选择
    std::cout << "选中的活动: 0 ";
    
    // 当前选择的活动的索引
    int current = 0;
    
    // 遍历其他活动
    for (int i = 1; i < activities.size(); i++) {
        // 如果当前活动的开始时间大于等于上一个选择的活动的结束时间，则选择该活动
        if (activities[i].start >= activities[current].end) {
            std::cout << i << " ";
            current = i;
        }
    }
}

int main() {
    std::vector<Activity> activities = { {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9},
                                         {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14} };
    
    activitySelection(activities);
    
    return 0;
}

在上面的代码中，我们定义了一个活动结构体来表示每个活动的开始时间和结束时间。然后，我们使用`std::sort`函数按照结束时间递增排序活动。接下来，我们从第一个活动开始，依次检查每个活动的开始时间是否大于等于上一个选择的活动的结束时间，如果是，则选择该活动。最后，我们输出选中的活动。

这就是一个使用贪心算法解决活动安排问题的C++代码示例。希望对你有所帮助！