algorithm - 间隔列表中范围非重叠间隔的最大总和

Question

有人问我这个问题:
您将获得一个间隔列表。你必须设计一个算法来找到非重叠区间的序列，使得区间范围的总和最大。

例如:
如果给定的间隔是:

["06:00","08:30"],
["09:00","11:00"],
["08:00","09:00"],
["09:00","11:30"],
["10:30","14:00"],
["12:00","14:00"]

三个区间时范围最大化

[“06:00”, “08:30”],
[“09:00”, “11:30”],
[“12:00”, “14:00”],

被选中。

因此，答案是420(分钟)。

Answer 1

这是一个标准的区间调度问题。
可以用动态规划求解。

算法
设 n 间隔。 sum[i] 在排序的区间数组中存储区间 i 的区间的最大总和。算法如下

Sort the intervals in order of their end timings.
sum[0] = 0
For interval i from 1 to n in sorted array
    j = interval in 1 to i-1 whose endtime is less than beginning time of interval i.
    If j exist, then sum[i] = max(sum[j]+duration[i],sum[i-1])
    else sum[i] = max(duration[i],sum[i-1])

迭代进行了 n 个步骤，在每个步骤中，可以使用二进制搜索找到 j，即在 log n 时间内。因此算法需要 O(n log n) 时间。