[Solution]Problem 14: Smallest Closed Interval [Google]

Sets, Intervals, Lists

Problem

This problem was asked by Google.

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}.

Step 1: Defining Intersecting Intervals

One of the tricky things about questions like this that they throw a lot of different things at you. We have multiple intervals, each of differing sizes. How do we define if two intervals intersect?

Let’s take [0, 3] and [2, 6]. Humans (or any other sentient beings of similar intelligence) would probably see that they both have the values [2,3]. Thus there is an overlap. In fact we can shorten the interval to [0,2] and this would work, but that’s for step 2.

How do we code this in? Generating the whole list can get out of hand (especially if we have huge intervals). One way to define the intersection of intervals is to go by what it’s not. The 0th index of our interval represents the lower bound. If that is more than the upper bound of the other index, we know that we don’t have intersecting intervals.

We code that in saying:

def intersecting(x, y): #x and y are both tuples representing intervals
    return not (x[0] > y[1] or y[0] > x[1])

Step 2: Tightening our bounds

Now that we have something that checks if two intervals intersect, we need to do make sure we pick the lowest bounds. How do we pick the smallest intersection b/w two intervals (assuming we know that they intersect)? We can have multiple kinds of intersections. The image below shows them.

Kinds of Intersections b/w sets

Let’s take [0, 3] and [2, 6]. The smallest intersection b/w them is [2,3]. This is the max of the lower bound and the min of the upper bound. Take a second to think of why this makes sense.

Step 3: Putting it all together

We have figured out the logic for 2 intervals? How do we generalize this to an arbitrary input? Simple, we go step by step. For a lot of comparison-based operations/questions, we can compare the first two elements, and use the result to compare to the third (and so forth).

def covering(intervals):

    result = []
    i = 0

    while i < len(intervals):
        interval = intervals[i]

        while i < len(intervals) and intersecting(intervals[i], interval):
            interval = (max(intervals[i][0], interval[0]), min(intervals[i][1], interval[1]))
            i += 1

        result.append(interval[1])
    return result

def intersecting(x, y):
    return not (x[0] > y[1] or y[0] > x[1])

This is a linear time solution despite the double for loops since we loop through the intervals. The result is a tuple so it is constant space

Final: O(n) Time and O(1) space

Bonuses/Promotion (Get Free Stuff)

Have anything to say to me? Use the links below.

To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.

To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:

Reach out to me on Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/