Merge Intervals — Solution

Problem

Given a list of intervals, merge any that overlap and return the smallest possible list of non-overlapping intervals. Two intervals overlap when the start of one falls at or before the end of the other.

• Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
• Output: [[1,6],[8,10],[15,18]]
• Explanation: [1,3] and [2,6] share the value 2, so they merge into [1,6].

Counter-example: [[1,4],[5,6]] does not merge because 5 > 4 — there is a gap between them.

Intuition

Once intervals are sorted by start time, an overlap can only occur between adjacent intervals — no later interval can skip over its neighbor to merge with something earlier. Walking the sorted list, we greedily extend the current interval whenever the next one starts before it ends.

Solution — Sort and Scan

Sort by start time, then walk through the list. If the next interval starts at or before the running end, extend the end. Otherwise, seal the current interval and open a new one.

1. Sort intervals by their start value.
2. Seed the result list with the first interval.
3. For each remaining interval, compare its start with the last result interval's end.
4. If they overlap (current_start ≤ last_end), update the last end to max(last_end, current_end).
5. Otherwise, append the current interval as a new entry.
6. Return the result list.

1def merge(intervals: list[list[int]]) -> list[list[int]]:
2    intervals.sort(key=lambda interval: interval[0])
3    merged = [intervals[0]]
4
5    for current_start, current_end in intervals[1:]:
6        last_end = merged[-1][1]
7        if current_start <= last_end:  # overlap: extend the running end
8            merged[-1][1] = max(last_end, current_end)
9        else:  # gap: seal current and open a new interval
10            merged.append([current_start, current_end])
11
12    return merged

Time: O(n log n) — sorting dominates; the scan afterward is O(n).
Space: O(n) — the result holds at most n intervals in the worst case.

Complexity Summary

Common Mistakes

• Skipping the sort — without sorting by start time, overlapping intervals may not be adjacent. For example [[1,5],[8,10],[3,6]] would leave [1,5] and [3,6] separate if you only compare each interval to its immediate neighbor in the original order.
• Using the new end instead of the max — writing merged[-1][1] = current_end instead of max(last_end, current_end) breaks when one interval is fully contained inside another. Input [[1,10],[2,3]] would incorrectly shrink to [1,3].
• Strict < instead of ≤ for the overlap check — current_start < last_end misses touching intervals like [1,3] and [3,5], which share the endpoint 3 and should merge to [1,5].
• Starting the scan at index 0 after seeding with intervals[0] — if you iterate intervals[0:] instead of intervals[1:], the first interval is processed twice and appears duplicated in the output.

Related Problems

• Insert Interval — same merging logic, but the list is already sorted and non-overlapping; you insert one new interval and merge in a single pass
• Non-Overlapping Intervals — the flip side: find the minimum number of intervals to remove so that no two overlap
• Partition Labels — partition a string so no character appears in two parts, which reduces to tracking each character's last occurrence as a range and merging those ranges greedily
• Find First and Last Position of Element in Sorted Array — locating the start and end boundaries of a contiguous range within sorted data