C++ 活动选择问题

活动选择是计算机科学中的一个经典问题，可以使用贪心算法解决。在这个问题中，我们给定一组要在给定时间内执行的活动，每个活动都有一个开始时间和一个结束时间。目标是选择可以执行的最大数量的活动，使得任何两个活动都不重叠。

让我们考虑一个例子来更好地理解这个问题。假设你有五个活动：A、B、C、D 和 E，每个活动的开始和结束时间如下：

A：开始 = 1，结束 = 4

B：开始 = 3，结束 = 5

C：开始 = 0，结束 = 6

D：开始 = 5，结束 = 7

E：开始 = 8，结束 = 9

我们可以看到，如果我们执行活动 A 和 D，就会发生冲突，因为这两个活动重叠。因此，目标是选择可以执行的最大数量的活动，且没有任何冲突。这个问题的解决方案可以使用贪心算法找到。贪心算法的思想是始终选择第一个完成的下一个活动。这确保我们有最大的时间来完成下一个活动。

以下是我们如何在 C++ 中实现活动选择问题：

C++ 代码

在上面的代码中，我们首先根据活动的结束时间对活动进行排序，因为我们希望选择第一个完成的活动。然后，我们使用两个指针 i 和 j 来跟踪当前活动和下一个活动。我们从 i = 0 和 j = 1 开始，并将下一个活动的开始时间与当前活动的结束时间进行比较。如果下一个活动的开始时间大于或等于当前活动的结束时间，我们可以在没有任何冲突的情况下执行这两个活动，因此我们递增 j 并设置 i = j。这会一直持续到 j 到达数组的末尾。此算法的时间复杂度为 O(n log n)，因为我们首先需要对活动进行排序，这需要 O(n log n) 的时间。此算法的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。

输出

Following activities are selected: 
(1, 2), (3, 4), (5, 7), (8, 9),

说明

上面的代码使用 C++ 中的贪心算法实现了活动选择问题。活动选择问题是计算机科学中的一个经典问题，其中我们给定一组要在给定时间内执行的活动，每个活动都有一个开始时间和一个结束时间。目标是选择可以执行的最大数量的活动，且没有任何冲突，使得任何两个活动都不重叠。

代码首先包含 bits/stdc++.h 头文件，其中包含所有标准 C++ 库。然后，定义 Activity 结构来存储每个活动的开始和结束时间。接下来，定义比较函数，用于根据活动的结束时间对活动进行排序。我们根据活动的结束时间对活动进行排序的原因是，我们希望选择第一个完成的活动。这确保我们有最大的时间来完成下一个活动。

printMaxActivities 函数将活动数组及其大小作为参数，并实现贪心算法来解决活动选择问题。该函数首先使用 sort 函数和比较函数根据活动的结束时间对活动进行排序。