C++ 活动安排问题：贪心算法优化与常见问题解析

活动安排问题是计算机科学中的经典问题，旨在从一系列活动中选择最佳的活动子集。常见的活动安排问题目标包括：

选择哪些活动可以使得总活动数最大；
选择哪些活动可以使得总活动时间最长；
选择哪些活动可以使得活动之间的时间冲突最少；
选择哪些活动可以使得每个时间段都有尽可能多的活动。

贪心算法解决活动安排问题

贪心算法是一种常用的解决活动安排问题的方法，它通过在每个步骤中做出局部最优选择来试图找到全局最优解。以下是针对不同目标的贪心算法解决思路：

最大活动数: 按照活动结束时间排序，选择结束时间最早的活动，然后再从剩余活动中选择结束时间最早的活动，直到所有活动都被选择完。
最长活动时间: 按照活动时间长度排序，选择时间长度最短的活动，然后再从剩余活动中选择时间长度最短的活动，直到总时间达到限制。
最小冲突: 按照活动结束时间排序，选择结束时间最早的活动，如果下一个活动的开始时间在当前活动结束时间之后，就将该活动加入选择列表，否则就忽略该活动。
时间段最大化: 按照活动时间长度排序，选择时间长度最短的活动，然后再从剩余活动中选择时间长度最短的活动，直到当前时间段无法再选择更多的活动为止，然后再从剩余活动中选择下一个时间段的第一个活动，重复上述步骤，直到所有时间段都被填满。

代码示例

// 以最大活动数为例，使用贪心算法解决活动安排问题
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Activity {
  int start;
  int end;
};

bool compareByEndTime(const Activity& a, const Activity& b) {
  return a.end < b.end;
}

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

  // 按照活动结束时间排序
  sort(activities.begin(), activities.end(), compareByEndTime);

  // 选择活动
  vector<Activity> selectedActivities;
  selectedActivities.push_back(activities[0]);
  int prevEndTime = activities[0].end;
  for (int i = 1; i < activities.size(); ++i) {
    if (activities[i].start >= prevEndTime) {
      selectedActivities.push_back(activities[i]);
      prevEndTime = activities[i].end;
    }
  }

  // 输出结果
  cout << '选择的活动：' << endl;
  for (const auto& activity : selectedActivities) {
    cout << '(' << activity.start << ', ' << activity.end << ')' << endl;
  }

  return 0;
}

总结

贪心算法可以有效地解决活动安排问题，但它并不总是能找到全局最优解。在选择贪心算法解决活动安排问题时，需要仔细分析问题特点，选择合适的排序策略和选择规则，才能获得最佳的活动安排方案。