Merge Intervals

Difficulty: Medium Source: NeetCode

Problem

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]]

Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]]

Constraints:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Sorting — sorting a list of pairs by the first element
• Intervals — recognising when two intervals overlap and how to merge them
• Greedy — extending the current merged interval as far right as possible before committing

1. Brute Force

Intuition

For every pair of intervals check whether they overlap, merge them if they do, and repeat until no further merges are possible. This is very slow but makes the logic crystal clear: two intervals [a,b] and [c,d] overlap whenever a <= d and c <= b.

Algorithm

1. Loop until no merges happen in a full pass:
   • For every ordered pair (i, j), if intervals[i] and intervals[j] overlap, replace them with their union and remove the other.
2. Return the remaining intervals.

Solution

def merge_brute(intervals):
    intervals = [list(x) for x in intervals]  # make a mutable copy
    merged = True
    while merged:
        merged = False
        for i in range(len(intervals)):
            for j in range(i + 1, len(intervals)):
                a, b = intervals[i]
                c, d = intervals[j]
                if a <= d and c <= b:  # overlap
                    intervals[i] = [min(a, c), max(b, d)]
                    intervals.pop(j)
                    merged = True
                    break
            if merged:
                break
    return sorted(intervals)


print(merge_brute([[1,3],[2,6],[8,10],[15,18]]))  # [[1,6],[8,10],[15,18]]
print(merge_brute([[1,4],[4,5]]))                 # [[1,5]]

Complexity

• Time: O(n³) — two nested loops, repeated until no merges remain
• Space: O(n) — copy of the input

2. Sort then Sweep

Intuition

Once we sort intervals by their start time, any interval that overlaps the previous one must start before or at the previous interval’s end. We walk through sorted intervals and either extend the current merged interval’s end or start a new one. A single pass after sorting is all we need.

Algorithm

1. Sort intervals by start time.
2. Push the first interval onto result.
3. For each subsequent interval [start, end]:
   • If start <= result[-1][1] (overlaps with last merged interval), update result[-1][1] = max(result[-1][1], end).
   • Otherwise append [start, end] as a new entry.
4. Return result.

Solution

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    result = [intervals[0]]

    for start, end in intervals[1:]:
        last_end = result[-1][1]
        if start <= last_end:
            # Overlapping — extend the last merged interval
            result[-1][1] = max(last_end, end)
        else:
            # No overlap — start a new merged interval
            result.append([start, end])

    return result


print(merge([[1,3],[2,6],[8,10],[15,18]]))  # [[1,6],[8,10],[15,18]]
print(merge([[1,4],[4,5]]))                 # [[1,5]]
print(merge([[1,4],[0,4]]))                 # [[0,4]]
print(merge([[1,4],[2,3]]))                 # [[1,4]]
print(merge([[1,2]]))                       # [[1,2]]

Complexity

• Time: O(n log n) — sorting dominates; the sweep is O(n)
• Space: O(n) — result list (O(log n) extra for the sort stack)

Common Pitfalls

Not taking the max of end times. When merging, use max(last_end, end) not just end. An interval can be completely contained inside another (e.g., [1,10] and [2,4]), so the contained interval’s end should not shrink the merged result.

Forgetting that touching intervals also merge. [1,4] and [4,5] share the point 4 and must merge into [1,5]. The overlap condition is start <= last_end (not strictly less than).

Sorting in place vs returning a copy. Python’s list.sort() sorts in place, which modifies the caller’s list. If that is unwanted, use sorted(intervals, ...) to get a fresh copy instead.