活动选择问题

问题

你有一系列的事情要做（活动）。每个活动都有一个开始时间和一个结束时间。你不能一次执行多项活动。你的任务是找到一种方法来执行最大数量的活动。

例如，假设你有一系列可供选择的类。

记住，你不能同时上两节课。这意味着你不能上 1 级和 2 级，因为他们共享一个共同的时间 10.30 AM 到 11.00 AM 然而，你可以参加 1 级和 3 级，因为他们没有共同的时间。因此，你的任务是尽可能获取最大数量的类，而不会有任何重叠。你怎么能这样做？

分析

让我们通过贪婪的方法来思考解决方案。首先，我们随机选择一些方法并检查是否有效。

• **按开始时间对活动进行排序，**这意味着首先从哪个活动开始我们将首先采取它们。然后从排序列表中取第一个到最后一个并检查它是否会与之前的活动相交。如果当前活动与之前采取的活动不相交，我们将执行活动，否则我们将无法执行。这种方法适用于某些情况

排序顺序为 4 - > 1 - > 2 - > 3.将执行活动 4 - > 1 - > 3，并跳过活动 2。将执行最多 3 项活动。它适用于此类情况。但在某些情况下会失败。让我们将这种方法应用于案例

排序顺序为 4 - > 1 - > 2 - > 3，仅执行活动 4，但答案可以是活动 1 - > 3 或 2 - > 3 将执行。因此，我们的方法不适用于上述情况。让我们尝试另一种方法

• **按持续时间对活动进行排序，**这意味着首先执行最短的活动。这可以解决以前的问题。虽然问题没有完全解决。仍有一些案例可能导致解决方案失败。在下面的案例中应用这种方法。

如果我们按持续时间对活动进行排序，则排序顺序为 2 - > 3 —> 1。如果我们先进行 2 号活动，那么就不能进行其他活动了。但答案是执行活动 1 然后执行 3。所以我们可以执行最多 2 个活动。所以这不能解决这个问题。我们应该尝试不同的方法。

解决方案

• **通过结束时间对活动进行排序，**这意味着活动首先完成。算法如下

1. 按活动结束时间对活动进行排序。
2. 如果要执行的活动与先前执行的活动不共享共同时间，请执行活动。

让我们分析第一个例子

按结束时间对活动进行排序，因此排序顺序为 1 - > 5 - > 2 - > 4 - > 3 ..答案为 1 - > 3 这两项活动将被执行。这就是答案。这是 sudo 代码。

1. 排序：活动
2. 从排序的活动列表中执行第一个活动。
3. 设置：Current_activity：=第一个活动
4. set：end_time：=当前活动的 end_time
5. 如果存在则转到下一个活动，如果不存在则终止。
6. 如果当前活动的 start_time <= end_time：执行活动并转到 4
7. 别的：得到 5。

请参阅此处获取编码帮助 http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/