题目描述：

有一组活动，每个活动都有一个开始时间和结束时间。你需要选择出最多数量的活动，使得这些活动之间没有重叠。

要求：

• 每个活动都有一个开始时间和结束时间，活动的时间是闭区间，即活动可以在其结束时间结束。
• 选择的活动必须是互不重叠的，也就是说，某个活动的结束时间必须小于下一个活动的开始时间。
• 你可以选择任意数量的活动，但要求选择最多的互不重叠的活动。

输入格式：

• 第一行包含一个整数 n，表示活动的数量。$1$ ≤ n ≤ $10^5$
• 接下来 n 行，每行包含两个整数 start[i] 和 end[i]，表示第 i 个活动的开始时间和结束时间。$1$ ≤ start[i] < end[i] ≤ $10^5$

输出格式：

• 输出一个整数，表示最多可以选择的互不重叠的活动数。

示例：

输入：

5
1 4
4 5
5 6
7 9
3 5

输出：

3

说明：

• 最多可以选择的互不重叠的活动是：活动 (1, 4)、活动 (5, 6)、活动 (7, 9)。
• 所以输出结果为 3。

【贪心3】活动选择

题目简述：

给定一组活动的开始时间和结束时间，每个活动的时间是一个闭区间，要求你选择出最多数量的活动，使得这些活动之间没有时间重叠。你需要找到最多可以选择多少个活动。

解题思路：

这道题是经典的“活动选择问题”，我们可以采用贪心算法来解决。

贪心策略：

1. 选择结束时间最早的活动：首先对活动按结束时间进行排序。然后从结束时间最早的活动开始选择，每次选择结束时间最早的活动，且前一个活动的结束时间必须小于下一个活动的开始时间，这样可以保证选择的活动之间没有重叠。

2. 贪心的正确性：

   在“最多不重叠区间选择”问题中，目标是从给定的一系列区间中，选择尽可能多的不重叠区间。这个问题是典型的贪心算法问题，常见的形式是“区间调度问题”（Interval Scheduling）。

   问题描述

   给定一组区间，每个区间由两个数表示：[start, end]，我们需要选择最多的互不重叠的区间，使得它们之间没有交集。

   贪心算法的思路

   对于这个问题，贪心策略是选择结束时间最早的区间，原因如下：

   1. 每次选择结束时间最早的区间，可以最大程度地留下剩余时间供后续的区间选择。
   2. 如果选择结束时间最早的区间，它将为下一个可能的区间选择提供更多的空间。

   贪心策略的正确性证明

   为了证明贪心策略是最优的，我们可以通过 交换引理（Exchange Argument）来证明贪心策略的正确性。

   1. 假设贪心解不是最优解

   假设存在一个最优解 S，但贪心算法的选择 G 比最优解 S 少选择了一个区间。我们需要证明可以通过交换 G 和 S 中的某些区间来使得 G 成为最优解。

   2. 选择贪心解

   在贪心算法中，每次选择结束时间最早的区间。假设在某一时刻，贪心算法选择了一个区间 I_g，而最优解 S 选择了一个区间 I_s，且 I_s 不是结束时间最早的区间。我们可以交换这两个区间的选择，将 I_s 替换为 I_g，并保持其他区间不变。

   3. 交换区间后的结果

   由于 I_g 的结束时间更早，它不会与 S 中已经选择的区间发生冲突。交换 I_s 和 I_g 后，得到的新的区间集 S' 仍然是一个有效的区间集，并且它包含的区间数量与最优解 S 相同，但它的结构与贪心算法的选择 G 更为接近。因此，S' 中的区间数至少与 G 相同。

   4. 重复交换

   继续对 S 中的每个区间进行类似的交换，直到所有区间都符合贪心算法的选择规则。最终，我们可以得到一个与贪心算法选择相同的解，且该解包含的区间数量最多。

   5. 结论

   通过交换引理，我们证明了贪心算法的选择是最优的，因为我们能够通过交换最优解中的区间，最终得到一个和贪心选择一样的解，并且区间数量也不会减少。

   总结

   • 贪心策略是选择结束时间最早的区间。
   • 通过交换引理，我们证明了贪心策略能够得到与最优解相同或更多的区间数量，因此它是最优的。
   • 最终证明贪心策略在“最多不重叠区间选择”问题中是正确的。

   例子

   假设我们有如下区间：[(1, 3), (2, 4), (3, 5), (4, 6), (5, 7)]，我们使用贪心算法选择结束时间最早的区间：

   1. 选择 (1, 3)，因为它的结束时间最早。
   2. 下一个可以选择的区间是 (3, 5)，因为它的开始时间是 3，不与 (1, 3) 重叠。
   3. 继续选择 (5, 7)，因为它的开始时间是 5，不与前一个区间 (3, 5) 重叠。

   最终，我们选择的区间是 [(1, 3), (3, 5), (5, 7)]，总共有 3 个不重叠区间。

   这与贪心策略所选择的区间数量一致，且它是最大可能数量的区间集。

复杂度分析：

• 排序复杂度：活动按照结束时间排序的复杂度是 O(n log n)，其中 n 是活动的数量。
• 选择活动的过程：选择活动的过程是线性的，即 O(n)。
• 总体时间复杂度是 O(n log n)。

代码实现：

def max_activities(n, activities):
    # 1. 按照活动的结束时间排序
    activities.sort(key=lambda x: x[1])
    
    # 2. 初始化选中的活动数量和上一个活动的结束时间
    count = 0
    last_end_time = -1
    
    # 3. 遍历所有活动，选择不与前一个活动重叠的活动
    for start, end in activities:
        # 如果当前活动的开始时间大于上一个活动的结束时间
        if start > last_end_time:
            count += 1  # 选择该活动
            last_end_time = end  # 更新上一个活动的结束时间为当前活动的结束时间
    
    return count

# 输入处理部分
n = int(input())  # 活动数量
activities = []
for _ in range(n):
    start, end = map(int, input().split())  # 每个活动的开始时间和结束时间
    activities.append((start, end))

# 输出最多可以选择的活动数
print(max_activities(n, activities))