给定一个 $n \times 2$ 的二维数组 arr[][]，表示 $n$ 个带有 起始 和 结束 点的 区间，我们的任务是找出这组区间中数量最多的 互不重叠 的子集。
注意： 如果两个区间 [i, j] 和 [k, l] 没有任何公共点，则称它们是 不重叠（或不相交）的。
示例：
> 输入： arr[][] = [[1, 4], [2, 3], [4, 6], [8, 9]]
> 输出：
> 2 3
> 4 6
> 8 9
> 解释： 如果我们包含了 [1, 4]，那么我们就不能包含 [2, 3] 和 [4 6]。
>
> 输入： arr[][] = [[1, 9], [2, 3], [5, 7]]
> 输出：
> 2 3
> 5 7
这个问题本质上是 活动选择问题 的一个变体。
[朴素方法] 生成所有子集 – $O(n^2 * 2^n)$ 时间复杂度和 $O(n)$ 空间复杂度
我们可以通过穷举所有可能的区间组合来解决这个问题。具体步骤如下：
- 生成给定区间集合的 所有子集。
- 通过比较起始和结束时间，检查子集是否仅包含互不重叠的区间。
- 记录下最大的有效子集。
C++
CODEBLOCK_7e57fdb3
Java
CODEBLOCK_36bd2dec
Python
CODEBLOCK_6a5ef870
[高效方法] 贪心算法 – $O(n \log n)$ 时间复杂度和 $O(1)$ 额外空间
虽然朴素方法可以解决问题，但其时间复杂度呈指数级增长，不适用于实际的大规模数据。让我们来学习一种更高效的贪心算法策略。这与活动选择问题的解法非常相似。
思路：
我们的目标是选取尽可能多的区间。如果我们总是优先选择结束时间最早的区间，那么就能为剩下的区间留出更多的时间空间。这是一种典型的贪心思想。
算法步骤：
- 排序： 首先，我们将所有区间按照 结束时间 进行升序排序。如果两个区间的结束时间相同，我们可以选择按起始时间排序（但这对于贪心策略的正确性不是必须的，只要按结束时间排即可）。
- 迭代选择： 初始化一个变量来记录上一个选中区间的结束时间（初始设为负无穷或第一个区间的结束时间）。遍历排序后的区间列表：
– 如果当前区间的 起始时间 大于或等于 上一个选中区间的结束时间，说明这两个区间不重叠。
– 我们将当前区间加入结果集，并更新“上一个选中区间的结束时间”为当前区间的结束时间。
– 否则，跳过当前区间（因为如果选了它，就会发生重叠，且由于我们是按结束时间排序的，选它肯定不如选之前那个结束得更早的区间优）。
让我们来看看具体的代码实现：
C++
CODEBLOCK_7f073563
Java
CODEBLOCK_8b3ff747
Python
CODEBLOCK_1414cfeb
复杂度分析：
- 时间复杂度： $O(n \log n)$。主要的时间开销在于对区间数组进行排序。遍历一次数组只需要 $O(n)$ 的时间。
- 空间复杂度： $O(1)$（如果忽略存储结果所需的输出空间）。我们不需要额外的空间来存储辅助数据结构（如果排序是原地进行的）。