带权重的活动选择问题（Weighted Interval Scheduling）

题目描述

给定一组活动，每个活动有一个开始时间、结束时间和权重（价值）。目标是选择一组互不重叠（即任意两个活动的时间段不重叠）的活动，使得所选活动的总权重最大。

解题过程

1. 问题分析

   • 每个活动有开始时间s_i、结束时间e_i和权重w_i
   • 需要选择互不重叠的活动子集
   • 目标是最大化总权重
   • 这是经典活动选择问题的加权版本

2. 关键思路

   • 按结束时间对活动排序
   • 对于每个活动，考虑两种选择：包含或不包含该活动
   • 如果包含当前活动，则不能包含与其时间重叠的活动

3. 动态规划定义

   • 定义dp[i]：考虑前i个活动（按结束时间排序）能获得的最大权重
   • 定义p[i]：在活动i之前结束且不与i冲突的最近活动的索引

4. 状态转移方程

   • 对于每个活动i，有两种选择：
     • 不选择活动i：dp[i] = dp[i-1]
     • 选择活动i：dp[i] = w_i + dp[p[i]]
   • 因此：dp[i] = max(dp[i-1], w_i + dp[p[i]])

5. 详细步骤

   步骤1：预处理

   • 将活动按结束时间从小到大排序
   • 计算p数组：对于每个活动i，找到最大的j使得e_j ≤ s_i

   步骤2：动态规划计算

   # 初始化
   dp[0] = 0  # 没有活动时权重为0
   
   # 按排序后的顺序处理每个活动
   for i in range(1, n+1):
       # 不选活动i vs 选活动i
       dp[i] = max(dp[i-1], weights[i] + dp[p[i]])
   

   步骤3：重构解

   • 从后往前追踪哪些活动被选中
   • 如果dp[i] > dp[i-1]，说明活动i被选中

6. 复杂度分析

   • 排序：O(n log n)
   • 计算p数组：O(n log n)（使用二分查找）
   • 动态规划：O(n)
   • 总复杂度：O(n log n)

7. 示例演示

   假设有4个活动：

   • 活动1: (1, 4, 5)
   • 活动2: (3, 5, 1)
   • 活动3: (0, 6, 8)
   • 活动4: (4, 7, 4)

   按结束时间排序：活动1(4), 活动2(5), 活动3(6), 活动4(7)

   计算p数组：

   • p[1] = 0 (活动1前没有不冲突的活动)
   • p[2] = 0 (活动2开始时间3，与活动1结束时间4冲突)
   • p[3] = 0
   • p[4] = 2 (活动4开始时间4，与活动2结束时间5不冲突)

   DP计算：

   • dp[0] = 0
   • dp[1] = max(0, 5+0) = 5
   • dp[2] = max(5, 1+0) = 5
   • dp[3] = max(5, 8+0) = 8
   • dp[4] = max(8, 4+5) = 9

   最优解：活动1和活动4，总权重9

这个算法通过巧妙的排序和p数组计算，高效解决了带权重的活动选择问题。