Efficient Algorithm for Grouping Intervals

1
votes

I need to find an algorithm that solves the following problem:

Given a list of intervals (leftBound,RightBound) which is the most efficient algorithm to group the intervals in this behavior:

Intervals: (1,4),(6,9),(1,3),(4,8),(6,9),(2,7),(10,15)

Wanted Solution:

Group (2,3) contains (1,3), (1,4), (2,7)

Group (6,8) contains (4,8), (6,9)

Group (10,15) contains (10,15)

Of course there are different possible solutions: (2,7) could also be in the second group instead.

My approach is to sort the intervals ascending by their left bound and if they have the same left bound descending by their right bound. Then i just loop over the sorted intervals and try to add them to the group I just build before. If this is not possible i build a new group for this interval and continue looping over the remaining orders.

Does this algorithm gurantee, that i receive the lowest possible numbers of different groups for my intervals? Could you say that this is a greedy approach for solving this problem?

1
algorithmschedulingintervalsgreedy
Sorting for the left bound only is sufficient. You will always add all intervals of the same left bound to the group. Yes this is greedy as you will add all you can and yes as your measure is the intersection you will get the minimal nuber of groups. - stefan
Thank you! But i just thought about the following scenario: (1,10) (2,3) (4,6) (8,9). My algorithm will result three different groups, but its possible to group the intervals in two groups. - FullyScaled
Please describe your valid grouping rules. - stefan
(1,10) (2,3) (4,6) (8,9) --> List is already sorted. First element in the loop is (1,10), so i create a group that contains this interval and has the left bound 1 and the right bound 10. The next element in the loop is (2,3). I try to add the Element to the group, i recently created. Since this is possible, my new left bound is now 2 and my right bound is 3. The group contains the first two Elements. Now i cannot add the third intervall to this group so i create a new group for it. Same for the fourth interval, which gives me three groups. - FullyScaled
Again, what is the rule for a valid group? Is (1,2) and (3,4) a valid group? Guess no. What about (1,6)(2,3)(4,5)? We cannot help you on algorithms if we do not know the problem. No examples please but a rule. - stefan

1 Answers

0
votes

Here is a suggestion:

  1. Sort by the right bound: (1,3), (1,4), (2,7), (4,8), (6,9), (6,9), (10,15).

  2. Create group with the lowest entry (rightBound - 1, rightBound) and remove it: (2,3): (1,3).

  3. Add all possible intervals to the group and remove them: (2,3): (1,3), (1,4), (2,7).

  4. Repeat 2. and 3. until the list is empty: 1. (2,3): (1,3), (1,4), (2,7); 2. (7,8): (4,8), (6,9), (6,9); 3. (14,15): (10, 15).

  5. Optional: enlarge the groups to their maximal size or use the lowest entry as group interval (2.) and increase the left bound when adding intervals (3.).

I think it should give the minimal number of groups because in step 2. we create a group which cannot be avoided and then in step 3. we add everything we can to it.