Algorithm - a group of overlapping intervals
I have a set of overlapping spacing, I have to select one item from the corresponding spacing so that when they are grouped, there are minimal gaps in the selection.
By grouping, I mean that successive elements are grouped. And if there are no consecutive elements from other intervals for an element, then it is considered as a group with one element
By minimizing gaps, I mean that we are reducing the number of such groups and trying to form larger
I saw about spacing trees and thought it might help, but not sure how to use that to my advantage
Please tell me what approach should be taken to solve the problem.
Example:
Intervals (including borders)
[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 selecting items above
2,3,4 and 9,10,11,12,13
So there is only one span 4-9
source to share
This issue was first addressed in:
R. Baptiste. Scheduler Tasks to Minimize the Number of Downtime Periods: A Polynomial Time Algorithm for Autonomous Dynamic Power Control. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, pages 364-367, Miami, Florida, 2006.
This article shows that there is a multi-term dynamic programming solution. Unfortunately, this is behind a paid wall.
However, there is also a paper :
Planning to minimize disruptions and energy consumption
Eric D. Demein, Mohammad Ghodsi, Mohammad Tagi Hajiaghayi Amin S. Saedi-Roshkhar, Morteza Zadimogaddam
which expands the problem to scheduling tasks on multiple processors and gives an O (n ^ 7p ^ 5) solution, where n is the number of intervals and p is the number of processors.
In your case p = 1, so this gives an O (n ^ 7) solution.
If it's too slow, you can also try the rough solution outlined in the doc, which tries to make each gap as large as possible.
source to share