3

我有一组重叠的间隔，我必须从相应的间隔中选择一个元素，这样当它们被分组时，选择中的间隔最小。

分组我的意思是连续的元素被分组。如果一个元素没有来自其他区间的连续元素，则将其视为具有一个元素的组

通过最小化差距，我的意思是，我们减少了此类群体的数量并尝试形成更大的群体

我看到了区间树，并认为这可能会有所帮助，但不确定如何为我的利益使用它

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

例子：

间隔（包括边界）

[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

通过选择上述元素组成的组

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

所以只有一个差距 4 到 9

4

1 回答 1

5

这个问题首先解决在：

P.巴蒂斯特。调度单元任务以最小化空闲期的数量：用于离线动态电源管理的多项式时间算法。在第 17 届 ACM-SIAM 离散算法年度研讨会论文集上，第 364-367 页，佛罗里达州迈阿密，2006 年。

本文表明存在动态规划多项式解。不幸的是，它位于付费墙后面。

但是，也有这篇论文：

调度以最小化间隙和功耗

作者：Erik D. Demaine、Mohammad Ghodsi、MohammadTaghi Hajiaghayi Amin S. Sayedi-Roshkhar、Morteza Zadimoghaddam

它将问题扩展到在多个处理器上调度任务并给出 O(n^7p^5) 解决方案，其中 n 是间隔数，p 是处理器数。

在您的情况下 p = 1，因此这给出了 O(n^7) 解决方案。

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

于 2014-09-24T18:58:43.050 回答