Algorithm - Group from the overlapping Intervals

Question

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.

Example:

Intervals (inclusive of boundaries)

[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

So there is only one gap 4 to 9

Answer 1

This problem was first solved in:

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.

However, there is also this paper:

Scheduling to Minimize Gaps and Power Consumption

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

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.

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.