算法 - 從重疊區間的組

Question

我有一組重疊區間，我必須從各自的區間中選擇一個元素，這樣當它們分組時，在選區中會有最小間隔。

通過分組我指的是連續的元素進行分組。如果有其他的時間間隔不連續元素的元素，然後這個被視爲組一個元素

通過儘量縮小差距我的意思是，我們必須減少這些羣體的數量，並嘗試形成較大的

我看到了間隔樹，認爲這可能有幫助，但不知道如何使用我的好處

請告訴我應該採取什麼方法來解決問題。

實例：通過選擇上述元素

2,3,4 and 9,10,11,12,13 

所以形成

間隔（包括邊界）

[1,2] 
[2,4] 
[3,7] 
[6,11] 
[9,11] 
[5,11] 
[10,14] 
[13,14] 

可能的解決方案

[1,2] ==> 2 
[2,4] ==> 3 
[3,7] ==> 4 
[6,11] ==> 10 
[9,11] ==> 9 
[5,11] ==> 11 
[10,14] ==> 12 
[13,14] ==> 13 

組再是隻有一個間隙4至9

Answer 1

此問題首先在解決：

P.巴普蒂斯特。調度單元任務最大限度地減少空閒時間段的數量：一個多項式時間算法，用於離線動態電源管理 。在上 離散算法的第17屆ACM-SIAM研討會論文集，頁364-367，邁阿密，佛羅里達州，2006年

本文表明，有一個動態規劃的多項式的解決方案。不幸的是它在付費牆後面。

然而，也有這個paper：

調度儘量縮小差距和功耗

由Erik D. Demaine，穆罕默德Ghodsi，MohammadTaghi Hajiaghayi 阿明S. Sayedi-Roshkhar，莫爾塔扎Zadimoghaddam

它將問題擴展到多個處理器上的調度任務並給出了一個O（n^7p^5）解決方案，其中n是間隔的數量，並且p nu大量的處理器。

在你的情況p = 1，所以這給出了一個O（n^7）的解決方案。

如果這太慢了，那麼你也可以嘗試在論文中描述的試圖使每個間隙儘可能大的近似解。