有人问我这样的问题：
您将获得一个间隔列表。您必须设计一种算法来找到不重叠间隔的序列，以使间隔范围的总和最大。
例如：
如果给定的间隔是：
["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（分钟）。
这是一个标准的区间调度问题。
可以用动态规划的方法来求解。
算法
让它有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) time.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
