DSAPrep
MediumIntervals

Merge Intervals

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Intervals [1,3] and [2,6] overlap, so merge them into [1,6].

Example 2

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping (they touch at 4).

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4
View original on LeetCode ↗

Brute Force (Repeated Pairwise Merging)

Time O(n³)Space O(n)

Repeatedly scan every pair of intervals; whenever two overlap, merge them into one and restart the scan. Stop when a full pass finds nothing left to merge.

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals = [iv[:] for iv in intervals]
        merged_any = True
        while merged_any:
            merged_any = False
            for i in range(len(intervals)):
                for j in range(i + 1, len(intervals)):
                    a, b = intervals[i], intervals[j]
                    if a[0] <= b[1] and b[0] <= a[1]:
                        a[0], a[1] = min(a[0], b[0]), max(a[1], b[1])
                        intervals.pop(j)
                        merged_any = True
                        break
                if merged_any:
                    break
        return intervals

Each pass costs O(n²) to find a mergeable pair, and up to O(n) merges may be needed — O(n³) worst case. It also never uses the fact that sorting would make overlaps trivial to spot.

Sort, Then Sweep

OptimalTime O(n log n)Space O(n)

Sort intervals by start time. Once sorted, any interval that overlaps the interval currently being built can only be the next one in order — so a single left-to-right sweep suffices: extend the last merged interval if the next one overlaps it, otherwise start a new one.

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

Tracing intervals = [[1,3],[2,6],[8,10],[15,18]] (already sorted by start):

Sorted intervals

[1, 3]
[2, 6]
[8, 10]
[15, 18]

Merged result

[1, 3]
1 / 4
mergingmerged

Sorted by start. Seed the result with the first interval, [1,3].

Why it’s correct: after sorting, if the next interval’s start is beyond the current merged interval’s end, nothing later can connect back to it either (everything after only has larger starts) — so it’s safe to close off the current interval for good. Complexity: dominated by the sort → O(n log n) time; the output list holds at most n intervals → O(n) space.