本文共 998 字，大约阅读时间需要 3 分钟。
活动选择问题是经典的贪心问题，解决方法如下：
按照活动的结束时间对活动进行排序。这样可以尽早释放时间，为后续选择留下更多空间。
初始化时，选择结束时间最早的活动作为第一个选中的活动，并记录其结束时间。
从第二个活动开始，依次检查每个活动的开始时间。如果当前活动的开始时间晚于或等于上一个活动的结束时间，则选择该活动，并更新结束时间。
通过这种方法，可以确保选择的活动数量最多。这是因为每次选择结束时间最早的活动，能够为后续的活动选择留下更多的时间窗口，从而最大化整体的活动数量。
以下是实现代码：
#include#include #include using namespace std;struct Activity { int start, end;};bool compare(const Activity& a, const Activity& b) { return a.end < b.end;}int main() { int n; cin >> n; vector acts(n); for (int i = 0; i < n; ++i) { cin >> acts[i].start >> acts[i].end; } sort(acts.begin(), acts.end(), compare); int last_end = acts[0].end; int count = 1; for (int i = 1; i < n; ++i) { if (acts[i].start >= last_end) { last_end = acts[i].end; count++; } } cout << count << endl; return 0;}
这个代码首先读取输入数据，定义了一个活动结构体，包含开始时间和结束时间。然后使用比较函数按结束时间排序活动。接着，初始化最后一个选中的活动的结束时间为第一个活动的结束时间，并遍历每个活动，选择不重叠的活动，最后输出选中的活动数量。
转载地址：http://jmtg.baihongyu.com/