加权单机区间调度

单机选择不重叠区间,使总权值最大;按右端点排序,用 DP 加二分前驱求解。

标签 动态规划 / 区间 / 排序 / 二分

题目描述

给定 𝑛 个区间 [𝑙𝑖,𝑟𝑖] 和权值 𝑤𝑖>0。选择若干两两不相交的区间,使总权值最大。

端点相接视为相容。

1≤𝑛≤2×105,0≤𝑙𝑖<𝑟𝑖≤109,1≤𝑤𝑖≤109。

题解

按右端点 𝑟𝑖 升序排序。设排序后第 𝑖 个区间为 𝐼𝑖,定义 𝑝𝑖 为最大的下标 𝑗<𝑖,使得 𝑟𝑗≤𝑙𝑖;不存在则 𝑝𝑖=0。由于右端点有序,可以用二分求 𝑝𝑖。

令 𝑓𝑖 表示只考虑前 𝑖 个区间时的最大总权值。对第 𝑖 个区间只有两种选择:

  • 不选:𝑓𝑖=𝑓𝑖−1;
  • 选:𝑓𝑖=𝑤𝑖+𝑓𝑝𝑖。

因此

𝑓𝑖=max(𝑓𝑖−1,𝑤𝑖+𝑓𝑝𝑖),𝑓0=0.

答案为 𝑓𝑛。

正确性来自最优子结构:若最优解选择 𝐼𝑖,它前面的区间必须全部在 𝐼𝑖 左侧结束,正好是前 𝑝𝑖 个区间;若不选,则最优解来自前 𝑖−1 个区间。

复杂度

排序为 𝑂(𝑛log𝑛),每个 𝑝𝑖 二分查找为 𝑂(log𝑛),DP 为 𝑂(𝑛)。总时间为 𝑂(𝑛log𝑛),空间为 𝑂(𝑛)。

参考

源码位置