Educative: Interactive Courses for Software Developers

Statement#

Given a sorted list of nonoverlapping intervals and a new interval, your task is to insert the new interval into the correct position while ensuring that the resulting list of intervals remains sorted and nonoverlapping. Each interval is a pair of nonnegative numbers, the first being the start time and the second being the end time of the interval.

Constraints:

$0 \leq$ existing_intervals.length $\leq 10^4$
existing_intervals[i].length, new_interval.length == 2
$0 \leq$ start time $<$ end time $\leq 10^4$
The list of intervals is sorted in ascending order based on the $start ~time$ .

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

The naive approach involves iterating through the list of intervals and checking for overlaps with a new interval. If overlap occurs, the new interval merges with the existing one. After iterating the entire list, if no overlap occurs, append the new interval. Finally, we sort the list based on the start times of the intervals to ensure the correct order of intervals.

Iterating through the intervals to merge or append the new interval based on overlaps takes $O(n)$ time, where $n$ represents the number of intervals. Then, sorting the output list takes $O(n \log n)$ time. Therefore, the overall time complexity of this solution is $O(n \log n)$ due to sorting being the dominant factor.

Optimized approach using the merge intervals pattern#

The problem requires us to do two things. First, we need to insert a new interval into a sequence of nonoverlapping intervals. Second, the result should also be a list of nonoverlapping intervals. This requires merging the new interval with any overlapping interval(s) in the input. Therefore, the merge interval pattern applies.

Step-by-step solution construction#

First, we process the intervals that start before the new interval and then insert the new interval itself. Additionally, we need to merge the new interval with the existing intervals in the input.

Here’s how we’ll implement this feature:

Since the intervals are sorted, we'll create an empty list, output, and start adding the intervals that start before the new interval.
Next, we'll add the new interval to the output list and merge it with the previously added interval if there is an overlap.
Finally, we'll add the remaining intervals to the output list, merging them with the previously added intervals when they overlap.

We’ll look at these steps and how they work individually to have a more comprehensive understanding of our solution. The first step is to see the new interval to be added and append all the intervals that start before it to a new list which we will use as our output later.

def insert_interval(existing_intervals, new_interval):
    # Read the starting and ending time of the new interval, into separate variables
    new_start, new_end = new_interval[0], new_interval[1]
    print("The new interval starts at ", new_start,
          " and ends at ", new_end, ".", sep="")
    # Initialize variables to help in iterating over the existing intervals list
    i = 0
    n = len(existing_intervals)
    print("There are", n, "intervals present in the list already.")
    # Initialize an empty list to store the output
    output = []
    # Append all intervals that start before the new interval to the output list
    print("Let's start adding these intervals into our output list one by one, until we come across an overlapping interval.")
    print("-" * 100)
    while i < n and existing_intervals[i][0] < new_start:
        output.append(existing_intervals[i])
        print("We can add", i + 1,
              "intervals in our new list without merging any intervals yet:")
        print(output)
        i = i + 1
        print("-" * 100)
        
# Driver code
def main():
    new_interval = [[5, 7], [8, 9], [10, 12], [1, 3], [1, 10]]
    existing_intervals = [
        [[1, 2], [3, 5], [6, 8]],
        [[1, 3], [5, 7], [10, 12]],
        [[8, 10], [12, 15]],

Enter to Rename, Shift+Enter to Preview

Insert Interval

def insert_interval(existing_intervals, new_interval):
    # Read the starting and ending time of the new interval, into separate variables
    new_start, new_end = new_interval[0], new_interval[1]
    print("The new interval starts at ", new_start,
          " and ends at ", new_end, ".", sep="")
    # Initialize variables to help in iterating over the existing intervals list
    i = 0
    n = len(existing_intervals)
    print("There are", n, "intervals present in the list already.")
    # Initialize an empty list to store the output
    output = []
    # Append all intervals that start before the new interval to the output list
    print("Let's start adding these intervals into our output list one by one, until we come across an overlapping interval.")
    print("-" * 100)
    while i < n and existing_intervals[i][0] < new_start:
        output.append(existing_intervals[i])
        i = i + 1
    print("The current output list of intervals without any overlapping intervals is:")
    print(output)
    # If the new interval starts after the end of the last interval appended to the output list,
    # just append the new interval to the output list.
    print("The output after merging this overlapping interval will be:")
    if not output or output[-1][1] < new_start:
        output.append(new_interval)
    # Otherwise merge the two intervals
    else:
        output[-1][1] = max(output[-1][1], new_end)
    print(output)
    print("-" * 100)

Enter to Rename, Shift+Enter to Preview

Insert Interval

In this step, we handle the remaining intervals in the existing interval list after adding the new interval. We iterate through the remaining intervals and merge them with the intervals in the output list if there is an overlap. By comparing start and end times, we determine if an interval should be appended or merged. This process ensures that all overlapping intervals are correctly merged into the output list.

Finally, we obtain the final output list representing the merged intervals from the existing and new intervals.

def insert_interval(existing_intervals, new_interval):
    # Read the starting and ending time of the new interval, into separate variables
    new_start, new_end = new_interval[0], new_interval[1]
    print("The new interval starts at ", new_start,
          " and ends at ", new_end, ".", sep="")
    # Initialize variables to help in iterating over the existing intervals list
    i = 0
    n = len(existing_intervals)
    print("There are", n, "intervals present in the list already. We append the intervals that have the starting point smaller than our new interval to add.")
    # Initialize an empty list to store the output
    output = []
    # Append all intervals that start before the new interval to the output list
    while i < n and existing_intervals[i][0] < new_start:
        output.append(existing_intervals[i])
        i = i + 1
    print("The output before we add the new interval is:", output)
    # If the new interval starts after the end of the last interval appended to the output list,
    # just append the new interval to the output list.
    if not output or output[-1][1] < new_start:
        output.append(new_interval)
    # Otherwise merge the two intervals
    else:
        output[-1][1] = max(output[-1][1], new_end)
        # Copy any remaining intervals to the output list,
    # similarly merging any overlaping intervals as we go
    while i < n:
        ei = existing_intervals[i]
        start, end = ei[0], ei[1]
        if output[-1][1] < start:

Enter to Rename, Shift+Enter to Preview

Insert Interval

def insert_interval(existing_intervals, new_interval):
    new_start, new_end = new_interval[0], new_interval[1]
    i = 0
    n = len(existing_intervals)
    output = []
    while i < n and existing_intervals[i][0] < new_start:
        output.append(existing_intervals[i])
        i = i + 1
    if not output or output[-1][1] < new_start:
        output.append(new_interval)
    else:
        output[-1][1] = max(output[-1][1], new_end)
    while i < n:
        ei = existing_intervals[i]
        start, end = ei[0], ei[1]
        if output[-1][1] < start:
            output.append(ei)
        else:
            output[-1][1] = max(output[-1][1], end)
        i += 1
    return output
# Driver code
def main():
    new_interval = [[5, 7], [8, 9], [10, 12], [1, 3], [1, 10]]
    existing_intervals = [
        [[1, 2], [3, 5], [6, 8]],
        [[1, 3], [5, 7], [10, 12]],
        [[8, 10], [12, 15]],
        [[5, 7], [8, 9]],
        [[3, 5]]

Enter to Rename, Shift+Enter to Preview

Insert Interval

Solution summary#

Append all intervals occurring before the new interval to the output list until we find an interval that starts after the starting point of the new interval.
If there is an overlap between the last interval in the output list and the new interval, merge them by updating the end value of the last interval. Otherwise, append the new interval to the output list.
Continue iterating through the remaining intervals and merge the overlapping intervals with the last interval in the output list.
Return the final output list containing the merged intervals.

Time complexity#

The time complexity is $O(n)$ , where $n$ is the number of intervals in the input list. This is because we iterate through the list once, checking and merging intervals as necessary.

Space complexity#

The space complexity is $O(1)$ , since we only use constant space other than the input and output data structures.

Solution: Insert Interval

Statement#

Solution#

Naive approach#

Optimized approach using the merge intervals pattern#

Step-by-step solution construction#

Just the code#

Solution summary#

Time complexity#

Space complexity#