的范围不重叠的时间间隔的间隔中的列表中的最大总和 [英] Maximum sum of the range non-overlapping intervals in a list of Intervals

问题描述

有人问我这个问题：
你正在给定间隔的列表。你必须设计一个算法，找到的非重叠的时间间隔的序列，使间隔的范围的总和为最大

Someone asked me this question:
You are given a list of intervals. You have to design an algorithm to find the sequence of non-overlapping intervals so that the sum of the range of intervals is maximum.

例如：
如果给定的时间间隔为：

For Example:
If given intervals are:

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

范围达到最大时，三个区间

Range is maximized when three intervals

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

进行选择。

因此​​，答案是420（分钟）。

Therefore, the answer is 420 (minutes).

推荐答案

这是一个标准的间隔调度问题。
它可以通过使用动态规划来解决。

This is a standard interval scheduling problem.
It can be solved by using dynamic programming.

算法
要有 N 的间隔。间隔长达间隔总和[I] 商店最高金额我在有序间隔排列。该算法如下

Algorithm
Let there be n intervals. sum[i] stores maximum sum of interval up to interval i in sorted interval array. The algorithm is as follows

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 步骤，在每个步骤中，Ĵ可以使用二进制搜索，即发现日志N 的时间。 因此算法将为O（n log n）的的时间。

The iteration goes for n steps and in each step, j can be found using binary search, i.e. in log n time. Hence algorithm takes O(n log n) time.

这篇关于的范围不重叠的时间间隔的间隔中的列表中的最大总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！