算法 - 集团的重叠区间 [英] Algorithm - Group from the overlapping Intervals

问题描述

我已经设置重叠的区间，我不得不选择从各区间的一个元素，这样当它们被分为有在选择最小差距。

I have set of overlapping intervals, i have to choose one element from the respective interval such that when they are grouped there are minimum gaps in the selection.

通过将我的意思是连续元素进行分组。如果有来自其它间隔不连续元素为那么这被认为是基带一种元素的元素

By Grouping I mean consecutive elements are grouped. And if there are no consecutive elements from other intervals for an element then this is considered as group with one element

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

By minimize gaps I mean, we have reduce number of such groups and try to form the larger ones

我看到了有关间隔树木，并认为这可能帮助，但不知道如何使用我的利益

I saw about interval trees and thought that might help but not sure how to use that for my benefit

请告诉我，我应该采取什么办法来解决这个问题。

Please tell me what approach should I take to solve the problem.

例如：

区间（含边界）

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

可能的解决方案

Possible Solution

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

通过选择上述因素形成的组

Groups formed by choosing above elements

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

因此​​，只有一个间隙4至9

So there is only one gap 4 to 9

推荐答案

在首次解决了这个问题：

This problem was first solved in:

P中。巴蒂斯特。调度单元的任务，以尽量减少空闲的数   周期：一个多项式时间算法离线动态功耗   管理。在第17届ACM-SIAM学术研讨会论文集   离散算法，364-367页，美国佛罗里达州迈阿密，   2006年。

P. Baptiste. Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, pages 364–367, Miami, Florida, 2006.

该文件表明，有一个动态规划的多项式的解决方案。不幸的是它的背后是一个付费墙。

This paper shows that there is a dynamic programming polynomial solution. Unfortunately it is behind a pay wall.

然而，也有这个本文：

调度尽量缩小差距和功耗

Scheduling to Minimize Gaps and Power Consumption

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

by Erik D. Demaine, Mohammad Ghodsi, MohammadTaghi Hajiaghayi Amin S. Sayedi-Roshkhar, Morteza Zadimoghaddam

延伸的问题，以在多处理器上调度任务，并提供一个为O（n ^ 7P ^ 5）解决方案，其中，n是时间间隔和p个处理器的数目。的数目

which extends the problem to scheduling tasks on multiple processors and gives a O(n^7p^5) solution where n is the number of intervals and p the number of processors.

在你的情况下，P = 1，所以这给出了一个为O（n ^ 7）解决方案。

In your case p=1, so this gives a O(n^7) solution.

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

If this is too slow, then you can also try the approximate solution described in the paper which tries to make each gap as large as possible.

这篇关于算法 - 集团的重叠区间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！