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.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.