算法 - 来自重叠间隔的分组

Question

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

通过分组我的意思是连续的元素被分组.如果元素的其他区间没有连续元素,则将其视为具有一个元素的组

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

我看到间隔树和思想可能有所帮助,但不知道如何使用它为我的利益

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

例:

间隔(包括边界)

[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的差距

Answer 1

这个问题首先解决了:

P. Baptiste.调度单元任务以最小化空闲周期的数量:用于离线动态功率管理的多项式时间算法.在第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)解.

如果这个太慢,那么你也可以尝试本文中描述的近似解决方案,试图使每个间隙尽可能大.