非重疊區間的貪婪選擇

Question

我試圖實現this paper（GBDP策略，「匹配距離」）中描述的算法，需要一點澄清。

基本上，問題是我有一個項目列表，其中每個項目有一個長度和間隔（它實際上是兩個區間，但它是相同的想法）。

ID LENGTH START END 
1  1000  1  1000 
2  20000  5  20005 
3  20  30500 30520 
4  500  30500 31000 
5  200  900  1100  

目標是找到具有非重疊範圍的項目子集。在論文中，他們說他們首先由長度

ID LENGTH START END 
2  20000  5  20005 
1  1000  1  1000 
4  500  30500 31000 
5  200  900  1100 
3  20  30500 30520 

對項目進行排序，然後進行「貪婪地選擇[項目]具有非重疊的時間間隔的一個子集」。這是我困惑的地方。我知道一個貪婪的算法是什麼，但我不確定這裏的作者是什麼意思。我猜想可能是他們只是通過清單，只保留那些不與上面那些重疊的項目。

ID LENGTH START END 
2  20000  5  20005 
4  500  30500 31000 
5  200  900  1100 
3  20  30500 30520 

注意，使用這種方法，結果仍然包括具有重疊範圍的項目（4和3）。

我設法在Perl中輕鬆實現這種方法，但我想這可能不是作者的意圖。他們的意思是保留與任何以上的其他項目不重疊的項目？如果有人在這種情況下解釋了「貪婪選擇」的含義，我會很感激。

Answer 1

你幾乎到最後是正確的（並且不是，你提出正確的解釋作爲選項）。

首先，正如你所說，從而使長度減少排序的事情：

ID LENGTH START END 
2  20000  5  20005 
4  500  30500 31000 
5  200  900  1100 
3  20  30500 30520 

現在我們貪婪，只要他們不前幾次的任何選擇了衝突選擇的時間間隔。因此，選定的組最初爲空，

1. 最初，2是我們可以做出的最貪婪的選擇（長度爲20000）。它不衝突，所以我們將它添加到所選集合中。
2. 同上4和5.選擇的集合現在是{2,4,5}。
3. 下一個貪婪（以及簡單剩餘）的選擇是3.因爲它與的任何衝突，即4，我們不能使用它。

因此，結果是{2,4,5}。

---

僅供參考，這與計算機科學中一個衆所周知的問題 - 區間調度密切相關。如果您嘗試優化總數的數字的匹配項，而不是總數長度的匹配項，您sort by end position and greedily choose。