MediumArraySortingIntervals

Merge Intervals

1 approach, code in every language

You are given a collection of intervals where each entry is written as a pair [start, end]. Some of these ranges may touch or overlap one another. Your task is to fuse every group of connected ranges into a single interval so that no two ranges in the result share any common ground.

Return a fresh list containing only the merged, non-overlapping intervals, and the intervals may be returned in any order that the checker accepts (sorted by start is the natural choice).

Example 1

Input: intervals = [[1,4],[3,6],[8,10],[9,12]]

Output: [[1,6],[8,12]]

1-4 and 3-6 touch, so they collapse into 1-6; 8-10 and 9-12 collapse into 8-12.

Example 2

Input: intervals = [[2,3],[3,5]]

Output: [[2,5]]

The two ranges meet exactly at 3, which still counts as overlapping, so they merge.

Constraints

1 ≤ intervals.length ≤ 10^4
intervals[i].length == 2
0 ≤ start ≤ end ≤ 10^4

Sort by start, then sweep

Order the intervals by their starting value and walk through them once, extending the last kept interval whenever the next one overlaps it.

Loading animation…

Intuition

If the intervals are lined up by their start point, then any interval that overlaps a given one must appear right after it. That lets us keep a single 'current' interval and either stretch its end when the next interval bleeds into it, or push a brand new interval when there is a clean gap. One left-to-right pass is enough because sorting has already grouped everything that could possibly connect.

Algorithm walkthrough

1Sort the input intervals in ascending order of their start value.
2Create an empty result list and iterate over each interval [start, end].
3If the result is empty or the current start is greater than the end of the last kept interval, append [start, end] as a new block.
4Otherwise there is an overlap, so raise the end of the last kept interval to the max of its end and the current end.
5After the pass, the result holds every merged, non-overlapping interval.

Implementation

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        merged = []
        for start, end in intervals:
            if merged and start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
        return merged

Time

O(n log n)

Space

O(n)

Sorting dominates the running time; the single sweep is linear. Output storage is O(n), and the sort itself may use up to O(log n) auxiliary space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Pipeline Sensor Coverage is our own problem on the technique behind Merge Intervals: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free