Insert Interval

Try to solve the Insert Interval problem.

We'll cover the following

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≤0 \leq existing_intervals.length ≤104\leq 10^4

  • existing_intervals[i].length, new_interval.length == 2

  • 0≤0 \leq start time << end time ≤104\leq 10^4

  • The list of intervals is sorted in ascending order based on the start timestart ~time.

Examples#

Created with Fabric.js 3.6.6 [5, 7] [8, 9] [10, 13] [1, 7] [1, 3] [8, 9] [10, 13] Existing intervals New intervals [2, 6] Output Sample example 1 Input We will merge [2, 6] with the first interval, [1, 3], to create [1, 6] andthen merge this interval with the next overlapping interval, [5, 7], tocreate [1, 7]. The intervals [8, 9] and [10, 13] don’t overlap with anyintervals, so they will exist independently.

1 of 2

Created with Fabric.js 3.6.6 [1, 3] Existing intervals New intervals Output [6, 9] [2, 5] [1, 5] [6, 9] Sample example 2 We will merge [2, 5] with the first interval, [1, 3], since they overlap tocreate a new interval [1, 5]. The interval, [6,9], will exist independently,since it doesn’t overlap with the other interval. Input

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check if you’re solving the correct problem:

Insert Interval

1

What will be the updated list of intervals?

existing_intervals = [[1,3],[4,5],[7,8],[9,12],[13,14]][[1, 3], [4, 5], [7, 8], [9, 12], [13, 14]]

new_interval = [2,10][2, 10]

A)

[[1,12],[13,14]][[1, 12], [13, 14]]

B)

[[1,3],[2,10],[4,5],[7,8],[9,12],[13,14]][[1, 3], [2, 10], [4, 5], [7, 8], [9, 12], [13, 14]]

C)

[[2,10],[13,14]][[2, 10], [13, 14]]

Question 1 of 40 attempted

Figure it out#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Iterate through the existing intervals and append all intervals occurring before the new interval to the output list.

Check if there is an overlap between the last interval in the output list and the new interval.

If there is an overlap, merge them by updating the end value of the last interval in the output list to the maximum of its current end time and the end time of the new interval.

Otherwise, append the new interval to the output list.

Continue iterating through the remaining intervals and merge any overlapping intervals with the last interval in the output list.

Return the final output list containing the merged intervals.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
Insert Interval

Merge Intervals: Introduction

Solution: Insert Interval