活动选择问题

活动选择问题（Activity Selection Problem）是一个经典的贪心算法问题，旨在从一组活动中选择最大数量的互不重叠的活动。每个活动可以用其开始时间和结束时间来表示。问题是在不改变活动顺序的前提下，选择最大数量的活动，使得选中的活动之间不会相互重叠。

以下是使用贪心算法解决活动选择问题的基本步骤：

1. 排序：按照活动的结束时间对所有活动进行排序。

2. 初始化：选择第一个活动，因为它的结束时间是最小的，所以它肯定是会被选中的。

3. 贪心选择：从第二个活动开始遍历所有活动，对于每个活动，执行以下操作：

   • 如果当前活动的开始时间大于前一个被选中活动的结束时间，则可以选中当前活动，因为它不会与前一个活动重叠。
   • 如果不能选中当前活动，则跳过它，继续检查下一个活动。

4. 计数：每选中一个活动，计数器增加1。

5. 结束条件：当所有活动都被检查过时，算法结束。

以下是活动选择问题的贪心算法伪代码：

function maxActivities(activities)
    sort activities by their end time
    selectedActivities := 0
    lastActivityEnd := 0
    for each activity in activities
        if activity.start > lastActivityEnd
            selectedActivities := selectedActivities + 1
            lastActivityEnd := activity.end
    return selectedActivities
end function

活动选择问题的时间复杂度是 O(n log n)，其中 n 是活动的数量，这是因为算法需要对活动进行排序。空间复杂度是 O(1)，因为除了输入数据外，我们只需要常数级别的额外空间。