Find the smallest set of numbers that covers all the intervals

December 24, 2023

Problem #

Given a set of closed intervals, find the smallest set of numbers that covers all the intervals. If there are multiple smallest sets, return any of them.

For example, given the intervals [0, 3], [2, 6], [3, 4], [6, 9], one set of numbers that covers all these intervals is {3, 6}.

Solution #

Here is the Python code to find the smallest set of numbers that covers all the given intervals:

def find_minimum_cover(intervals):
    # Sort intervals based on the end points
    intervals.sort(key=lambda x: x[1])

    result = []
    last_added = float('-inf')

    for interval in intervals:
        # If the start of the current interval is greater than the last added point,
        # it means the current interval is not covered
        if interval[0] > last_added:
            # Add the end of the current interval to the result
            result.append(interval[1])
            last_added = interval[1]

    return result

# Example intervals
intervals = [[0, 3], [2, 6], [3, 4], [6, 9]]

# Find minimum cover
minimum_cover = find_minimum_cover(intervals)

For the given intervals ([0, 3], [2, 6], [3, 4], [6, 9]), this code finds that the set ({3, 9}) covers all the intervals. Note that this solution finds one of the possible smallest sets, and there may be other sets that also satisfy the condition.

Checking and Adding Points:

if interval[0] > last_added:
    result.append(interval[1])
    last_added = interval[1]

For each interval, the code checks if the start of the interval (interval[0]) is greater than last_added. If it is, it means that the current interval is not covered by any of the numbers added to result so far. Therefore, the end of this interval (interval[1]) is added to result, and last_added is updated to this value.