Given some integer ranges, finding a smallest set containing at least one integer from each range

Question

How can I find a set of minimum number of integers such that, for some given ranges of integers, for each range, the set contains at least one integer. For example, if I'm given these ranges :

[0, 4], [1, 2], [5, 7], [6, 7], [6, 9], [8, 10]

Then some solution sets are : { 1, 6, 8 }, { 2, 7, 9 }, { 1, 7, 8 } etc.

Answer 1

Imagine you draw all your ranges, ordered by end value, as you would draw meetings inside a day planner.

You can visually choose your numbers in a greedy manner, such that the first one is the segment that finishes first (in your example, that would be 2).

Then you erase all segments that contain that number, and you start all over.

This algo would yield solution { 2, 7, 10 }

0  1  2  3  4  5  6  7  8  9 10
   ----
-------------
      ^        -------
      |           ----
                  ----------
                     ^  -------
                     |        ^
                              |

Answer 2

Algorithm: Sort the start and end points. Pass over them until you meet an endpoint. Add it to the answer and remove all ranges which startpoints already passed (i.e. which contain current endpoint). Repeat until there's any point left.

Example:

[0, 4], [1, 2], [5, 7], [6, 7], [6, 9], [8, 10]

After sorting will become

[0, [1, 2], 4], [5, [6, [6, 7], 7], [8, 9], 10], ans = []

First endpoint is 2], we add it to ans and remove ranges opened before it, i.e. [0 and [1:

[5, [6, [6, 7], 7], [8, 9], 10], ans = [2]

Now first endpoint is 7] and we remove ranges [5, 7], [6, 7], [6, 9]:

[8, 9], ans = [2, 7]

Finally add 9 and remove the last range. The result will be [2, 7, 9].

Complexity:

Sorting will take O(nlogn) time, after that you'll pass on each element twice: once when looking for next endpoing and once when removing all currently opened intervals, which is linear, and total complexity will be O(nlogn) which comes from sorting.

Answer 3

We sort the intervals by the end numbers. For any interval, if its start is not greater than the previous end, (end is not smaller than the previous end since the intervals have been sorted), then we have an overlap at the previous end, and can skip this interval. If the start of the current interval is greater than the previous end, we have no overlap, and add the current end to the result set.

Consider the intervals (0, 3), (2, 6), (3, 4), (6, 10). After sorting, we have (0, 3), (3, 4), (2, 6), (6, 10). We start with result = [3] and previous = 3. Since 3 <= previous, we skip the interval (3, 4); previous remains unchanged. Since 2 <= previous, we skip the interval (2, 6); previous remains unchanged. Lastly, since 6 > previous, we add 10 to the result, and update previous = 10. The algorithm terminates; the answer is [3, 10].

Time complexity: n log(n), where n is the number of intervals.