P3110. 观看文艺汇演

解题思路

注意，本题和 无重叠区间 几乎完全一致。

原始数据处理

我们可以储存每一场演出的开始和结束时间，即按照 [start, end] 的方式进行储存，储存在列表 intervals 中。由于题目要求 每间隔 15 分钟 才能够看下一场演出，所以我们可以把每一场演出的结束时间再加上 15 分钟，这样题目就转变为：考虑所有不重叠的 `[start, end]` 区间的最大数目。处理输入的代码如下：

贪心思想求解问题

为了方便我们贪心地思考问题，我们先按照 开始时间 `start` 从小到大对间隔列表 intervals 进行排序。

两个区间之间的关系

然后我们考虑相邻的两场演出，[start1, end1] 和 [start2, end2]，由于 intervals 已经排序，必然存在 start1 <= start2 成立，故这两场演出之间的关系存只有以下三种可能性：

1. `start1 < end1 <= start2 < end2`，即演出 2 的开始时间在演出 1 的结束时间之后。故看完演出 1，可以继续看演出 2。 2. `start1 <= start2 <= end1 <= end2`，即演出 2 的开始时间在演出 1 的结束时间之前，但演出 2 的结束时间在演出 1 的结束时间之后。故看完演出 1 之后，没办法观看演出 2。而且 选择演出 1 进行观看是更划算的，因为它结束得更早，预留出更多的时间去观看后续的演出。 3. `start1 <= start2 <= end2 <= end1`，即演出 2 的开始时间和结束时间均在演出 1 的结束时间之前。故看完演出 1 之后，没办法观看演出 2。为了尽可能多地看更多的演出，在选择观看的演出时，我们会 直接选择演出 2 而不是演出 1（即使演出 1 的开始时间更早），因为演出 2 的结束时间更早，有充裕的时间去观看后续的演出。

贪心地讨论所有区间

理解了相邻两场演出的三种可能性之后，我们发现解决问题的关键实际上在于考虑 演出 1 的结束时间 `end1` 和 演出 2 的间隔 `[start2, end2]` 之间的关系：

• end1 在 [start2, end2] 之前
• end1 在 [start2, end2] 之间
• end1 在 [start2, end2] 之后

由于我们需要遍历排序后的间隔列表 intervals 中的每一个间隔 [start, end]。因此可以维护变量 `pre_end`，表示上一场演出的结束时间。初始化 pre_end = -inf，表示第一场演出始终可以观看。

考虑当前间隔 [start, end] 和上一场演出结束时间 pre_end 之间的关系，我们可以得到以下逻辑：

• 当 `pre_end` 在 `[start, end]` 之前，我们可以选择当前的演出 [start, end] 进行观看（对应情况 1）。能观看的演出场次 ans += 1。由于选择了 [start, end] 进行观看，下一场演出的观看时间应该由当前的 end 决定，即对于下一场演出而言，当前结束时间 end 是上一场演出的结束时间，故更新 pre_end = end。
• 当 `pre_end` 在 `[start, end]` 之间，我们不能选择当前的演出 [start, end] 进行观看（对应情况 2）。由于 pre_end ≤ end，因此我们保留之前的 pre_end，作为判断下一场演出是否能观看的依据。故无需做任何事情。
• 当 `pre_end` 在 `[start, end]` 之后，我们不能选择上一场的演出进行观看，而需要用观看当前这场演出 [start, end] 来代替上一场演出 [pre_start, pre_end]（对应情况 3）。由于 pre_end > end，选择 end 作为判断下一场演出是否能观看的依据是更佳的选择，即我们不去选择观看 pre_end 所对应的之前某场演出，而选择观看当前的演出 [start, end]，这样的选择有利于后面留出充裕的时间来尽可能地观看更多演出，故更新 pre_end = end。

整理上述逻辑后，代码为：

动态规划求解问题

实际上，当我们对间隔列表 intervals 排序之后，我们也可以把这个问题当作经典的 LIS 问题（最长递增子序列）进行处理。

譬如对于上述例子，我们所选的演出应该为演出 1、4、5。换句话说，我们需要找到尽可能多的演出区间，所有演出区间均需要满足 start ≥ pre_end，其中 start 为第 i 个区间的开始时间，pre_end 为上一个区间即第 i-1 个区间的结束时间。这是一个非常自然的 LIS 问题，故也可以用 dp 来解决问题。

我们考虑动态规划三部曲：

• dp 数组的含义是什么？

dp 数组是一个长度为 n 的一维列表，dp[i] 表示 包含了第 `i` 场演出 `intervals[i]` 的最长无重叠演出数目。

• 动态转移方程是什么？

包含了第 i 场演出 intervals[i] 的最长无重叠演出数目，由前面的 i-1 场演出中（用索引 j 表示），结束时间 intervals[j][1] 小于当前演出开始时间 intervals[i][0] 且 dp[j] 最大的那场演出决定。

• dp 数组如何初始化？

包含第 1 场演出的最长无重叠演出数目为 1。 dp[0] = 1

代码

解法一：贪心

复杂度分析

• 设演出场数为 N。参考代码（贪心解法）分三步：读入并构造区间（结束时间统一加 15 分钟转场，随读入顺带完成），O(N)；按开始时间对区间排序，O(N log N)，这是整体瓶颈；随后一个 for 循环遍历全部区间，每个区间只做常数次比较并更新 ans、preEnd，O(N)。整体时间复杂度为 O(N log N)。
• 空间上需要存放 N 个区间对象，O(N)；遍历本身只用 ans 与 preEnd 两个变量，额外辅助空间 O(1)。
• 正文中给出的动态规划（LIS 式）解法是双重循环：对每个 i 都要回看前面所有 j，时间复杂度为 O(N^2)，另需 dp 数组 O(N) 空间。演出场数较大时贪心明显更优，DP 版本更适合作为思路对照与正确性验证。