Insert Interval

Patrick Leaton
Published: June 5, 2021, 3:57 p.m.
Problem Description

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

 

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

Example 3:

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4:

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

Example 5:

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

 

Constraints:

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= intervals[i][0] <= intervals[i][1] <= 10^5
  • intervals is sorted by intervals[i][0] in ascending order.
  • newInterval.length == 2
  • 0 <= newInterval[0] <= newInterval[1] <= 10^5

 

The description was taken from https://leetcode.com/problems/insert-interval/.

Problem Solution

#O(N) Time, O(1) Additional Space
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        output = []
        place = 0
 
        for start, end in intervals:
            if start < newInterval[0]:
                output.append([start,end])
                place += 1
            else:
                break
 
        if not output or output[-1][1] < newInterval[0]:
            output.append(newInterval)
        else:
            output[-1][1] = max(output[-1][1], newInterval[1])
 
        for start, end in intervals[place::]:
            if output[-1][1] < start:
                output.append([start, end])
            else:
                output[-1][1] = max(output[-1][1], end)
 
        return output

Problem Explanation

This question is like a sequel to the Merge Intervals question.

The solution is like we would expect.  We will traverse the intervals we already have until we find an overlap in times with the interval we are trying to insert.  When that happens, we will continuously merge the current interval's end-time with the previous interval's end time, if it overlaps.

Let's start by initializing our intervals output and the interval we will need to merge our insertion interval into, initially none.

        output = []
        place = 0

 

Then, we will begin our traversal and in each iteration, if the current interval starts before the insertion interval starts, we will append it to the output and increment our place in the array by one.

When merging intervals, we will want to keep the lowest start time and the greatest end time.  This is us keeping the lowest start time between the last interval and the insertion interval.

Once we find the interval that has a greater start time than the insertion interval, we will break.  

        for start, end in intervals:
            if start < newInterval[0]:
                output.append([start,end])
                place += 1
            else:
                break

 

Let's go ahead and draw this out.  This is key with interval problems.

We'll take this test case:

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

 

Here we would append red to the output since its start time is less than blue's.  

          
                             
 
                
<1-2-3-4-5-6-7-8-9>
output = [[1,3]]

 

If we don't need to merge our interval because the last interval in the output ends before the insertion interval starts, we will just place the new interval into the output.

        if not output or output[-1][1] < newInterval[0]:
            output.append(newInterval)

 

Otherwise, like in our example, we will need to merge the insertion interval into the last interval placed in the overlapping output.

We will merge by giving the last interval in the output the greatest end-time between itself and the insertion interval.

 

                

                             
<1-2-3-4-5-6-7-8-9>
output = [[1,5]]
 
        else:
            output[-1][1] = max(output[-1][1], newInterval[1])

 

Then, from the last interval placed in the output onward, we will check if the last interval in the output ends before the current one starts.

        for start, end in intervals[place::]:
            if output[-1][1] < start:

 

If that is true, there is no overlap so we can just throw the current interval into the output.  That is like our example.

                
                             
<1-2-3-4-5-6-7-8-9>
output = [[1,5], [6,9]]

                output.append([start, end])

 

Otherwise, we will need to merge again.

We will merge by giving the last interval in the output the greatest end-time between itself and the current interval.

            else:
                output[-1][1] = max(output[-1][1], end)

 

Once we have traversed the list, we will return the output of the new intervals.

        return output