56. Merge Intervals

The Merge Intervals problem is a classic introduction to the Intervals pattern. It is a favorite in interviews because it tests whether you can turn many possible overlap comparisons into a single, ordered pass. While repeatedly merging pairs may seem straightforward, this problem proves why sorting first is essential for merging ranges efficiently and correctly.

Problem statement

Given a list of intervals, where each interval is [start, end]. Our task is to merge every pair of overlapping intervals and return a new list containing only non-overlapping intervals, while still covering the full range represented by the original input.

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits does not contain any leading 0‘s.

Examples

Naive approach

A naive approach is to use a nested loop to compare every pair of intervals: the outer loop picks an interval i, and the inner loop checks it against every later interval j where j > i. For each pair (i, j), you check whether they overlap. For intervals [a, b] and [c, d], an overlap exists if a <= d and c <= b. If you find an overlapping pair, merge them into a single interval, replace it with the original interval in the list, and then restart the scan from the beginning, as the newly merged interval may now overlap with intervals you have already processed. In the worst case, you end up doing many repeated passes over the same ranges, which becomes too slow when there are up to 10⁴ intervals.

Optimal solution using Intervals

Overlaps become much easier to handle once we sort the intervals by start time. Once the intervals are in sorted order, each new interval presents only two possibilities: either it merges into the current range, or it starts a new one. For each subsequent interval, we compare it with the last merged range.

•  If the next interval starts after the current interval ends, there’s no overlap, so you append the current interval and process the next interval.
• Otherwise, the next interval starts before or at the current end, which means they overlap, so you merge them by extending the current end to max(current_end, next_end). 

Repeat this process until all intervals have been processed.

Why do touching endpoints still merge? 

As the problem treats intervals like [1, 4] and [4, 5] as overlapping, so our overlap rule must be next_start <= current_end (not strictly < ). Using <= ensures that even intervals that share only an endpoint merge into a single continuous range, allowing the left-to-right traversal to work cleanly without additional conditions.

Algorithmic steps

This algorithm is implemented as follows:

1. Sort intervals by their start time start.
2. Create an empty list merged.
3. iterate through intervals in sorted order.
   1. If merged is empty or the current interval does not overlap with the last merged one,
      1. Append it.
   2. Otherwise,
      1. Merge by updating the last interval’s end to max(last_end, current_end).
4. In the end, return merged.

To better understand the solution, let’s walk through the algorithm using the illustration below:

1 / 7

Python implementation 

The code below implements the algorithm described above.

def merge(intervals):
    """
    Merge overlapping intervals using sorting + greedy merging.

    Strategy:
    1) Sort intervals by start time.
    2) Walk through them and merge into the last interval whenever overlap occurs.
    """

    # Sort by start time so overlaps become local (only need to check the last merged interval).
    intervals.sort(key=lambda x: x[0])

    merged = []

    for start, end in intervals:
        # If merged is empty OR current interval doesn't overlap with the last merged one,
        # we start a new merged interval.
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            # Overlap exists, so extend the last merged interval's end boundary.
            merged[-1][1] = max(merged[-1][1], end)

    return merged


def main():
    test_cases = [
        [[1, 3], [2, 6], [8, 10], [15, 18]],   # standard overlap
        [[1, 4], [4, 5]],                      # touching endpoints
        [[4, 7], [1, 4]],                      # unsorted input
        [[1, 10], [2, 3], [4, 8]],             # fully contained intervals
        [[1, 2], [3, 4], [5, 6]]               # no overlaps
    ]

    for i, intervals in enumerate(test_cases, 1):
        result = merge(intervals)
        print(f"  {i}. \t Input: {intervals}")
        print(f"\t Output: {result}")
        print("-"*75)


if __name__ == "__main__":
    main()

Time complexity

The time complexity of the solution is O(n log n) because we sort the nnn intervals first. After sorting, we perform a single pass through the list to merge, which is why sorting dominates.

Space complexity

The space complexity of this solution is O(n) because, in the worst case, the output list may contain all intervals if none overlap. Sorting may also use additional space depending on the language/runtime, but the dominant explicit extra space is the merged output.

Common pitfalls to avoid

• Forgetting to sort first: Without sorting, you can miss merges because overlapping intervals might not be adjacent in the input.
• Using the wrong overlap condition: If you check start >= last_end instead of start > last_end, you’ll incorrectly split intervals.
• Not extending the end properly: When overlapping, you must set end = max(current_end, next_end), not just overwrite it.
• Mutating references incorrectly: Be careful if you store references to original sublists; it’s usually safer to build merged intervals explicitly as shown.