移除区间的最小成本问题 题目描述 给定一个区间列表 intervals ，其中每个区间表示为 [start, end] 。你希望移除一些区间，使得剩余的区间互不重叠（即任意两个区间都没有重叠部分）。移除一个区间 [start, end] 的成本是 end - start （即区间的长度）。你的目标是找到一组要移除的区间，使得剩余区间互不重叠，且移除的总成本最小。返回这个最小总成本。 例如： 输入： intervals = [[1, 3], [2, 4], [3, 5], [6, 7]] 输出： 3 解释：移除区间 [2, 4] 成本为 2，移除区间 [3, 5] 成本为 2，总成本为 4 不是最小。最佳方案是移除 [2, 4] 和 [3, 5] 中的一个（成本 2），并保留 [1, 3] 和 [6, 7] ，但这样仍然有重叠。正确方案是移除 [1, 3] （成本 2）和 [3, 5] （成本 2）？不对，这样剩下 [2, 4] 和 [6, 7] 不重叠，但成本是 4。实际上，最优是移除 [2, 4] （成本 2）和 [3, 5] （成本 2）？不对，这样剩下 [1, 3] 和 [6, 7] 不重叠，但成本是 4。但例子输出是 3，意思是移除 [2, 4] 和 [6, 7] ？不， [6, 7] 与其他都不重叠。让我们重新看：区间为 [ 1,3], [ 2,4], [ 3,5], [ 6,7]。如果只移除 [ 2,4]（成本 2），剩下 [ 1,3] 和 [ 3,5] 在点 3 重叠（端点相接是否算重叠？通常区间重叠定义为区间 i 的结束 > 区间 j 的开始，且区间 j 的结束 > 区间 i 的开始，这里 [ 1,3] 和 [ 3,5] 在 3 相接不算重叠，因为第一个区间结束等于第二个区间开始，通常不算重叠）。所以保留 [ 1,3] 和 [ 3,5] 和 [ 6,7] 是合法的，无需移除更多，成本 0？不对，因为 [ 2,4] 与两者都重叠。保留 [ 1,3] 和 [ 3,5] 的话，必须移除 [ 2,4]，成本 2，但总移除成本是 2，不是 3。但答案是 3，说明对重叠的定义可能是端点相接也算重叠（即区间是闭区间，[ 1,3] 和 [ 3,5] 在 3 处重叠了）。按照通常力扣 435. 无重叠区间（最少移除数量）的定义，边界相接不算重叠。但这里我们要求最小移除总长度，而不是最少数量。我们定义：如果两个区间有公共点（包括端点），则重叠。那么 [ 1,3] 和 [ 3,5] 重叠，[ 2,4] 和 [ 1,3] 重叠，也和 [ 3,5] 重叠。所以 [ 1,3], [ 2,4], [ 3,5] 两两重叠。要使得剩下不重叠，只能保留其中一个区间，加上 [ 6,7 ]。所以有三种选择： 保留 [ 1,3] 和 [ 6,7]，移除 [ 2,4] (长度 2) 和 [ 3,5 ] (长度 2)，总移除成本 4。 保留 [ 2,4] 和 [ 6,7]，移除 [ 1,3] (2) 和 [ 3,5 ] (2)，总成本 4。 保留 [ 3,5] 和 [ 6,7]，移除 [ 1,3] (2) 和 [ 2,4 ] (2)，总成本 4。 都不等于 3。 检查例子输出 3 的可能性：如果只移除一个区间 [ 2,4] (成本 2) 不能解决问题，因为剩下 [ 1,3] 和 [ 3,5] 重叠（如果端点相接算重叠）。如果只移除 [ 3,5] (成本 2)，剩下 [ 1,3] 和 [ 2,4] 重叠。如果只移除 [ 1,3] (成本 2)，剩下 [ 2,4] 和 [ 3,5 ] 重叠。 如果移除两个区间，比如移除 [ 2,4] 和 [ 3,5] (成本 4)，剩下 [ 1,3] 和 [ 6,7 ] 不重叠，成本 4。 但答案是 3，意味着可能可以部分重叠？不，题目是移除整个区间，不是切掉部分。 实际上，这道题是 给定带权区间，选一个最大权（这里权是区间长度）的不重叠子集 ，那么最小移除成本 = 总区间总长 - 最大保留总长度。 总长度：(3-1)+(4-2)+(5-3)+(7-6) = 2+2+2+1 = 7。 最大不重叠区间集合的总长度：选择 [ 1,3] 和 [ 6,7] 总长 2+1=3，或者 [ 2,4] 和 [ 6,7] 总长 2+1=3，或者 [ 3,5] 和 [ 6,7 ] 总长 2+1=3。 所以最大保留总长度是 3，那么最小移除成本 = 7 - 3 = 4。但答案是 3，矛盾。 可能例子是我编的。我们换一个例子： 输入： intervals = [[1, 2], [2, 3], [3, 4], [1, 3]] 总长度 = 1+1+1+2 = 5。 不重叠区间集合：选 [ 1,2], [ 2,3], [ 3,4 ] 是端点相接，如果不算重叠则可以全保留，保留总长 3，移除成本 2。如果端点相接不算重叠，则最大保留总长 3，最小移除成本 2。 如果端点相接算重叠，则只能选两个区间，比如 [ 1,2] 和 [ 3,4] 总长 2，或 [ 2,3] 和 [ 1,3 ] 不行（重叠），等等。最大保留总长 2，移除成本 3。 常见题目是 最小移除区间数以使得不重叠 （力扣 435），这里是 最小移除区间总长度 ，是加权版本。 我们明确题目： 区间重叠定义为区间 i 的结束 > 区间 j 的开始 且 区间 j 的结束 > 区间 i 的开始（即严格重叠，端点相接不算重叠）。我们要移除一些区间，使得剩下的区间互不重叠，且移除的区间总长度最小。 这样，例子 [[1, 3], [2, 4], [3, 5], [6, 7]] ： 总长度 = 2+2+2+1=7。 最大保留不重叠区间的总长度：可以保留 [ 1,3] 和 [ 3,5] 和 [ 6,7]，因为 [ 1,3] 和 [ 3,5] 端点相接不算重叠，所以保留总长 2+2+1=5，那么移除成本 = 7-5=2，只需移除 [ 2,4 ] 即可。但这样是移除一个区间，成本 2，不是 3。 所以原例子可能假设端点相接算重叠，这样最大保留不重叠区间总长：只能保留一个长 2 的区间和 [ 6,7 ]，总长 3，移除成本 4。 我查一下常见题：实际上是 带权区间调度最大权 ，即每个区间有权值（这里是长度），求不重叠区间的最大总权值。那么移除最小成本 = 总权值和 - 最大权值和。 我们以这个定义为准来讲题。 所以问题转化为：给定 n 个区间，每个区间有权值 w_ i = end_ i - start_ i，选出权值和最大的不重叠区间集合。 解题过程 步骤 1：排序 为了用动态规划，我们首先按区间结束时间升序排序。 设区间编号 1 到 n，按 end 排序后，区间顺序为 [ start[ i], end[ i], weight[ i] ]。 步骤 2：定义状态 定义 dp[i] 为考虑前 i 个区间（按结束时间排序），且 必须选第 i 个区间 时，能获得的最大权值和。 为什么定义必须选第 i 个区间？因为这样方便状态转移：当我们决定选第 i 个区间时，需要找到之前最后一个不重叠的区间 j，使得 end[ j] <= start[ i ]。 另一种定义： dp[i] 表示前 i 个区间中能选出的不重叠区间的最大权值和（不一定选第 i 个）。 但常用的是第一种，便于转移。 我们这里用第二种更直观： dp[i] 表示考虑前 i 个区间（排序后），能获得的最大权值和（不重叠）。 步骤 3：状态转移 对于第 i 个区间，有两种选择： 不选第 i 个区间，则 dp[i] = dp[i-1] 。 选第 i 个区间，则我们需要找到最大的 j < i，使得 end[ j] <= start[ i]（即最后一个不与 i 重叠的区间）。那么 dp[i] = dp[j] + weight[i] 。 取两者最大值。 如何快速找到这样的 j？可以在排序后对每个 i 二分查找最大的 j 满足 end[ j] <= start[ i ]。 步骤 4：初始化 dp[0] = 0 表示没有区间时权值和为 0。 我们可以在区间数组前加一个虚拟区间 0，结束时间 -∞，方便处理。 步骤 5：最终答案 最大不重叠权值和 = dp[n] （如果 dp 下标从 1 到 n）。 那么最小移除成本 = 所有权值总和 - 最大不重叠权值和。 步骤 6：算法流程 按 end 排序所有区间。 计算每个区间的权值 = end - start。 计算前缀最大 dp 值。 设 dp[i] 表示前 i 个区间（按排序后）的最大权值和。 设 p[i] 表示对于区间 i，最后一个结束时间 <= start[ i ] 的区间索引（二分查找得到）。 转移： dp[i] = max(dp[i-1], dp[p[i]] + weight[i]) 。 答案 = 总权值和 - dp[ n ]。 举例说明 区间： [[1, 3], [2, 4], [3, 5], [6, 7]] ，权值：[ 2, 2, 2, 1 ]，总权值和 = 7。 按 end 排序后： [[1,3], [2,4], [3,5], [6,7]] （已经有序）。 计算 p[ i ]： i=1: start=1，找 end <=1 的区间，没有，p[ 1 ]=0。 i=2: start=2，找 end <=2 的区间，没有，p[ 2 ]=0。 i=3: start=3，找 end <=3 的区间，区间 1 的 end=3 满足，p[ 3 ]=1。 i=4: start=6，找 end <=6 的区间，区间 3 的 end=5 满足，p[ 4 ]=3。 dp[ 0 ]=0。 dp[ 1] = max(dp[ 0], dp[ p[ 1]]+w1) = max(0, dp[ 0 ]+2)=2。 dp[ 2] = max(dp[ 1], dp[ p[ 2]]+w2) = max(2, dp[ 0 ]+2)=max(2,2)=2。 dp[ 3] = max(dp[ 2], dp[ p[ 3]]+w3) = max(2, dp[ 1 ]+2)=max(2,4)=4。 dp[ 4] = max(dp[ 3], dp[ p[ 4]]+w4) = max(4, dp[ 3 ]+1)=max(4,5)=5。 最大不重叠权值和 = 5，最小移除成本 = 7-5=2。 验证：保留区间 [ 1,3], [ 3,5], [ 6,7] 不重叠（端点相接不算重叠），总权值和=2+2+1=5，移除 [ 2,4 ] 成本 2。 复杂度 排序 O(n log n)，二分查找 n 次 O(n log n)，总 O(n log n)，空间 O(n)。 关键点 排序按结束时间。 二分查找前一个不重叠区间。 状态转移取 max(不选当前区间, 选当前区间+前一个不重叠的 dp 值)。 最终答案为总权值和减最大权值和。