算法找出加權重疊區間的權重總和最高的區間

Question

嗯，我認爲這很難解釋，所以我已經做了一個數字來表明。

正如我們在這個圖中看到的，有時間的6個時段。每個人都有自己的重量。不透明度越高，重量越高。我想要一個算法來找出總和權重最高的區間。在這個圖的情況下，它將是間隔5和6的重疊，這是不透明度最高的區域。

Answer 1

• 將每個間隔拆分爲開始點和結束點。

• 對點進行排序。

• 從0開始，

• 迭代通過使用點和一個sweep-line algorithm：

  • 如果你得到一個起點：

    • 通過增加總和相應間隔的值。

    • 如果總數高於迄今爲止的最佳總數，請存儲此起始點並設置一個標誌。

  • 如果你得到一個終點：

    • 如果設置了標誌，存儲存儲的起點和當前總和爲最佳間隔這個終點到目前爲止並重置旗。

    • 將計數值減少相應間隔的值。

這是從the answer I wrote here，這是基於非加權版本，即衍生查找重疊的間隔的最大數目，而不是最大求和重量。

實施例：

對於這個例子：作爲

的開始/結束點進行排序：（S =啓動，E =端）

1S, 1E, 2S, 3S, 2E, 3E, 4S, 5S, 4E, 6S, 5E, 6E 

通過它們迭代，你會在上設置標誌，5S和6S，並且您將分別存儲1E,4E和5E（這是您在上述開始點之後獲得的第一個終點）的間隔。

您不會在2S，3S或4S上設置標誌，因爲總和將低於目前爲止的最佳總和。

Answer 2

算法邏輯可以從圖中得出。假設時間間隔的該分辨率爲1分鐘，然後陣列可以被創建並用於所有的計算：

1. 創建的24 * 60個元件的陣列，並用0權重填寫;
2. 對於每個時間間隔將此間隔的權重添加到數組的相應部分;
3. 通過迭代數組找到最大的總和權重;
4. 再次遍歷數組，並輸出數組索引（時間）與最大總和權重。

如果您需要在輸出中有間隔索引，則可以修改此算法以執行稍微不同的任務。在這種情況下，數組應包含輸入時間間隔索引的列表作爲第二維（或者它可以是一個單獨的數組，取決於特定的語言）。

UPD。我很好奇，如果這個簡單的算法比@Dukeling建議的更優雅的算法慢得多。我編碼了兩種算法並創建了一個輸入生成器來估計它們的性能。

發生器：

#!/bin/sh 
awk -v n=$1 ' 
BEGIN { 
    tmax = 24 * 60; wmax = 100; 
    for (i = 0; i < n; i++) { 
    t1 = int(rand() * tmax); 
    t2 = int(rand() * tmax); 
    w = int(rand() * wmax); 
    if (t2 >= t1) {print t1, t2, w} else {print t2, t1, w} 
    } 
}' | sort -n > i.txt 

算法＃1：

#!/bin/sh 
awk ' 
{t1[++i] = $1; t2[i] = $2; w[i] = $3} 
END { 
    for (i in t1) { 
    for (t = t1[i]; t <= t2[i]; t++) { 
     W[t] += w[i]; 
    } 
    } 
    Wmax = 0.; 
    for (t in W){ 
    if (W[t] > Wmax) {Wmax = W[t]} 
    } 
    print Wmax; 
    for (t in W){ 
    if (W[t] == Wmax) {print t} 
    } 
} 
' i.txt > a1.txt 

算法＃2：

#!/bin/sh 
awk ' 
{t1[++i] = $1; t2[i] = $2; w[i] = $3} 
END { 
    for (i in t1) { 
    p[t1[i] "a" i] = i "S"; 
    p[t2[i] "b" i] = i "E"; 
    } 
    n = asorti(p, psorted, "@ind_num_asc"); 
    W = 0.; Wmax = 0.; f = 0; 
    for (i = 1; i <= n; i++){ 
    P = p[psorted[i] ]; 
    k = int(P); 
    if (index(P, "S") > 0) { 
     W += w[k]; 
     if (W > Wmax) { 
     f = 1; 
     Wmax = W; 
     to1 = t1[k] 
     } 
    } 
    else { 
     if (f != 0) { 
     to2 = t2[k]; 
     f = 0 
     } 
     W -= w[k]; 
    } 
    } 
    print Wmax, to1 "-" to2 
} 
' i.txt > a2.txt 

結果：

$ ./gen.sh 1000 
$ time ./a1.sh 
real 0m0.283s 
$ time ./a2.sh 
real 0m0.019s 
$ cat a1.txt 
24618 
757 
$ cat a2.txt 
24618 757-757 
$ ./gen.sh 10000 
$ time ./a1.sh 
real 0m3.026s 
$ time ./a2.sh 
real 0m0.144s 
$ cat a1.txt 
252452 
746 
$ cat a2.txt 
252452 746-746 
$ ./gen.sh 100000 
$ time ./a1.sh 
real 0m34.127s 
$ time ./a2.sh 
real 0m1.999s 
$ cat a1.txt 
2484719 
714 
$ cat a2.txt 
2484719 714-714 

簡單就慢了20倍。