带备用活动的Activity Selection Problem求解咨询

问题回顾 #

我们需要选择最大的非重叠主活动集合U，满足每个主活动u∈U都能匹配到一个不在U中的备用活动v，且v仅与u重叠（或不重叠，但不能与U中其他活动重叠），备用活动可在多个主活动间共享。

原方法的缺陷：先选基础最大活动集合再尝试匹配备用，失败则递减规模，这种方式可能错过更优的可行集合，且退减过程效率低下。

核心思路 #

通过预处理活动的前后依赖关系，结合动态规划（DP）和离线区间统计，直接计算出符合条件的最大主活动集合，避免试错退减。

详细步骤 #

1. 活动排序 #

将所有活动按结束时间从小到大排序，记为数组A，每个元素为(start, end)。这是活动选择问题的常规预处理，时间复杂度O(NlogN)。

2. 预处理前后依赖数组 #

为每个活动计算两个关键索引：

• prev[i]：数组A中，第i个活动之前（结束时间≤第i个活动开始时间）的最后一个活动的索引。若不存在这样的活动，设为-1。
  • 实现：对每个i，用二分查找在A[0..i-1]中找最大的j满足A[j].end ≤ A[i].start，时间复杂度O(NlogN)。
• next[i]：数组A中，第i个活动之后（开始时间≥第i个活动结束时间）的第一个活动的索引。若不存在这样的活动，设为N（N为活动总数）。
  • 实现：对每个i，用二分查找在A[i+1..N-1]中找最小的j满足A[j].start ≥ A[i].end，时间复杂度O(NlogN)。

3. 离线统计每个活动的可用备用数 #

对每个活动i，计算其“保护区间”[L_i, R_i]：

• L_i = A[prev[i]].end（若prev[i] = -1，则L_i = -∞）
• R_i = A[next[i]].start（若next[i] = N，则R_i = +∞）

统计保护区间内的活动总数cnt[i]（包含活动i本身）。若cnt[i] ≥ 2，说明除了i之外还有至少一个活动可作为备用，i可以被选为主活动。

统计实现（离线处理，O(NlogN)）

1. 收集所有查询：每个活动i对应查询(L_i, R_i)，需统计满足start ≥ L_i且end ≤ R_i的活动数量。
2. 将所有活动和查询按end从小到大排序：活动的排序键为end，查询的排序键为R_i。
3. 用有序列表（通过二分维护）逐步插入活动的start值，同时处理查询：
   • 遍历排序后的活动和查询，遇到活动则将其start插入有序列表。
   • 遇到查询时，用二分查找找到有序列表中第一个≥L_i的位置，活动数量为列表长度 - 该位置索引，此即为cnt[i]。

4. 动态规划计算最大主活动数 #

定义dp[k]为考虑前k个活动（即A[0]到A[k-1]）时，能选出的符合条件的最大主活动数。

状态转移

• dp[0] = 0（无活动时数量为0）
• 对每个k从1到N：
  1. 不选第k个活动：dp[k] = dp[k-1]
  2. 选第k个活动：若cnt[k-1] ≥ 2，则：
     • 若prev[k-1] = -1，option = 1
     • 否则，option = dp[prev[k-1] + 1] + 1
     • 更新dp[k] = max(dp[k], option)

DP过程时间复杂度为O(N)。

5. 结果 #

dp[N]即为符合条件的最大主活动集合的大小。

关键优势 #

• 时间复杂度严格O(NlogN)，无试错退减过程，效率极高。
• 直接针对问题约束建模，避免原方法中“选最大基础集合后无法匹配备用”的情况，确保结果最优。

内容的提问来源于stack exchange，提问作者Szyszka947