algorithm - 區間列表中區間非重疊區間的最大求和

  显示原文与译文双语对照的内容
77 1

有人問我這個問題:
你得到了一系列的時間間隔。 你必須設計一個演算法來找到非重疊間隔的序列,以便間隔範圍的和是最大值。

例如:
如果給定的間隔為:


["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 ( 分鐘) 。

时间: 原作者:

110 5

這是一個標準的間隔調度問題。
它可以通過動態編程來解決。

演算法
n 間隔。 sum[i] 在排序的間隔 array 中存儲最大間隔和間隔 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) 時間。

原作者:
...