假设您有k<=10^5个区间[a_i, b_i]∈[1,10^18](其中一些可能重叠),您需要选择一组互不相交的区间,使它们的并集最大化。不是最大数量的不相交区间,而是并集必须覆盖最多。
不能尝试所有可能的子集2 ^ k是不可行的。 贪心方法按a_i排序(区间覆盖算法)和按b_i排序(最大不相交区间算法)都不起作用 无法确定是否存在动态程序解决方案。 考虑到输入的大小,我认为解决方案应该是O(k log k)或O(k)
示例 1. [1,4],[3,5],[5,9],[7,18] Sol [3,5]u[7,18]
2. [1,2],[2,6],[3,4],[5,7] Sol [1,2]u[3,4]u[5,7]
3. [2,30],[25,39],[30,40] Sol [2,30]
不能尝试所有可能的子集2 ^ k是不可行的。 贪心方法按a_i排序(区间覆盖算法)和按b_i排序(最大不相交区间算法)都不起作用 无法确定是否存在动态程序解决方案。 考虑到输入的大小,我认为解决方案应该是O(k log k)或O(k)
示例 1. [1,4],[3,5],[5,9],[7,18] Sol [3,5]u[7,18]
2. [1,2],[2,6],[3,4],[5,7] Sol [1,2]u[3,4]u[5,7]
3. [2,30],[25,39],[30,40] Sol [2,30]
dp[i]
= 以第i
个段结束的最大联合。如果您正确跟踪事件(或使用类似于线段树的数据结构),则可以在O(k log k)
时间内完成。 - kraskevich