算法 - 从重叠区间的组

问题描述：

我有一组重叠区间，我必须从各自的区间中选择一个元素，这样当它们分组时，在选区中会有最小间隔。算法 - 从重叠区间的组

通过分组我指的是连续的元素进行分组。如果有其他的时间间隔不连续元素的元素，然后这个被视为组一个元素

通过尽量缩小差距我的意思是，我们必须减少这些群体的数量，并尝试形成较大的

我看到了间隔树，认为这可能有帮助，但不知道如何使用我的好处

请告诉我应该采取什么方法来解决问题。

实例：通过选择上述元素

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

阐述你的问题，目前还不清楚。 – 2014-09-24 15:27:54

是的，特别是，你想尽量减少什么？连续差距的总和？你确定你需要间隔树吗？ – user189 2014-09-24 16:18:56

你能提供一个例子吗？这将有助于我们理解你的问题。 – gaborsch 2014-09-24 17:52:42

答

此问题首先在解决：

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）的解决方案。

如果这太慢了，那么你也可以尝试在论文中描述的试图使每个间隙尽可能大的近似解。