Google Technical Phone Screen Question: Insert Interval

Today’s problem involves merging intervals. This is a medium-difficulty problem that comes up frequently in Google technical interviews.

The problem is:

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the ith interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

Output: [[1,2],[3,10],[12,16]]

Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Observations

Let’s make sure we understand the question first.

We see that in the first example, [1,3] and [2,5] are overlapping intervals. We can merge these to make [1,5].

What operation are we doing here? How do we know that these intervals overlap?

A key observation is that the second element of the first interval is greater than the first element of the second interval. (Note an overlapping interval could also have these two values be *equal*!)

Another key observation is that we need these intervals to be sorted by their first value in ascending order. For example, if I have [[3,5], [1,1]], and I apply the rule above, I would mistakenly think these two intervals overlap. However, if I’m looking at [[1,1],[3,5]], then apply the above rule, I know these intervals don’t overlap.

So, let’s first sort the array by the first value in each interval, in ascending order.

Algorithm

How should we go about processing this array?

Since we have a *new* interval to insert, let’s think about when we would need to insert it. When do we *not* need to worry about merging intervals?

Looking at the second example:

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

How do I know that I don’t need to touch the [1,2] interval? Well, the start of my new interval (4) is greater than the end of that interval (2), so I don’t need to worry about [1,2].

But I do know there’s some merging going on with the [3,5], because the start of my new interval (4) is less than 5.

So for the intervals that are strictly before my new interval, I can just append those to my result output first.

Now, when we get to the part where we *do* need to merge, then I’ll apply the merging logic I had above: while the end of my new interval is greater than or equal to the start of the next interval, I’ll take the minimum of the starts and maximum of the ends to get my merged interval.

How do I know when to stop my merging logic?

Well, when the end of my merged interval is less than the start of the next interval to look at, then I know I can just append the rest of the intervals in the original array to my output, and return that.

Code

Let’s see how the code looks:

Algorithmic Complexity

Runtime complexity: O(N log N), because we’re using a sort.

Space complexity: O(N), because we’re making a new array to hold the output, which is the size of the original input with an additional interval in it.

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!