Merge Intervals

Try to solve the Merge Intervals problem.

We'll cover the following

Statement#

We are given an array of closed intervals, intervals, where each interval has a start time and an end time. The input array is sorted with respect to the start times of each interval. For example, intervals = [ [1,4], [3,6], [7,9] ][~[1,4], ~[3,6], ~[7,9]~] is sorted in terms of start times 1, 31, ~3, and 77.

Your task is to merge the overlapping intervals and return a new output array consisting of only the non-overlapping intervals.

Constraints:

  • 1≤1 \leq intervals.length ≤104\leq 10^4
  • intervals[i].length =2= 2
  • 0≤0 \leq start time ≤\leq end time ≤104\leq 10^4

Examples#

Created with Fabric.js 3.6.6 1, 8 Intervals [1, 5], [3, 7], [4, 6], [6, 8] are overlapping.Merge them to one interval [1, 8]. Input Intervals array 1, 5 3, 7 4, 6 6, 8 Sample example 1

1 of 3

Created with Fabric.js 3.6.6 Intervals array 10, 12 12, 15 10, 15 Intervals [10, 12], [12, 15] are overlapping.Merge them to one interval [10, 15]. Input Sample example 2

2 of 3

Created with Fabric.js 3.6.6 Input Intervals array 1, 3 2, 6 8, 10 15, 18 18, 20 Intervals [1, 3] and [2, 6] overlap and are merged to [1, 6].Intervals [15, 18] and [18, 20] overlap and are merged to [15, 20]. 1, 6 8, 10 15, 20 Sample example 3

3 of 3

Understand the problem#

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

Merge Intervals

1

Given the below intervals, find the correct output after merging the overlapping intervals.

[ [1, 6], [2, 4] ]

A)

[ [2, 4] ]

B)

[ [1, 6] ]

C)

[ [1, 6], [2, 4] ]

D)

[ [2, 4], [1, 6] ]

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.

Insert the first interval from the input list into the output list.

Start a loop to iterate over each interval of the input list, except for the first.

If the input interval is overlapping with the last interval in the output list, merge these two intervals and replace the last interval of the output list with this merged interval.

Otherwise, if the input interval does not overlap with the last interval in the output list, add the input interval to the output list.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Merge Intervals

Solution: Insert Interval

Solution: Merge Intervals