Mastering the Merge Intervals Problem in Python

Mastering the Merge Intervals Problem in Python

If you're studying data structures and algorithms, the Merge Intervals problem is a foundational exercise.

As a senior software engineer and educator in this space, I've taught this concept extensively, especially in Python.

In this article, we’ll walk through both a brute-force and optimal solution, breaking down the core ideas for anyone — even beginners.

What Is the Merge Intervals Problem?

You're given a list of intervals like this: [[1,3], [2,6], [8,10]], and your job is to merge any overlapping intervals. The result should be a simplified version with no overlaps.

Example:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Brute-Force Approach Using compare

First, let’s look at an intuitive but inefficient solution. We manually compare each pair and try to merge them if they overlap.
from typing import List

def compare(a, b):
    """Check if two intervals overlap and return the merged one if they do."""
    if a[0] <= b[0] <= a[1] and b[1] > a[1]:
        return [a[0], b[1]], True
    elif b[0] <= a[0] <= b[1] and a[1] > b[1]:
        return [b[0], a[1]], True
    elif a[0] <= b[0] and a[1] >= b[1]:
        return a, True
    elif b[0] <= a[0] and b[1] >= a[1]:
        return b, True
    elif a[1] == b[0] or b[1] == a[0]:
        return [min(a[0], b[0]), max(a[1], b[1])], True
    return [], False


def merge_intervals(nums: List[List[int]]) -> List[List[int]]:
    """Inefficient merging of overlapping intervals using compare function."""
    if not nums:
        return []

    nums.sort()  # Sorting helps reduce randomness
    result = [nums[0]]

    for i in range(1, len(nums)):
        merged, status = compare(result[-1], nums[i])
        if status:
            result[-1] = merged
        else:
            result.append(nums[i])

    return result

Limitations

    • Time complexity: O(n^2) due to repeated comparisons.
    • Not scalable for large inputs like 10^6 intervals.

Optimal Solution

The key to performance is sorting the intervals first and only comparing the current interval with the last one in the result list.

from typing import List

def merge_intervals(nums: List[List[int]]) -> List[List[int]]:

    """Efficiently merge overlapping intervals."""
    if not nums:
        return []

    # Step 1: Sort by start of interval
    nums.sort(key=lambda x: x[0])
    merged = [nums[0]]

    # Step 2: Iterate and merge where needed
    for current in nums[1:]:
        prev = merged[-1]
        if current[0] <= prev[1]:  # Overlapping
            prev[1] = max(prev[1], current[1])
        else:
            merged.append(current)

    return merged

Time and Space Complexity

    • Time: O(n log n) due to sorting
    • Space: O(n) for storing the output

This solution is ideal for handling large datasets like:

Testing the Function

Here are some common edge and stress tests:

import unittest

class TestMergeIntervals(unittest.TestCase):
    def test_1(self):
        self.assertEqual([[1,6],[8,10],[15,18]], merge_intervals([[1,3],[2,6],[8,10],[15,18]]))

    def test_2(self):
        self.assertEqual([[1,5]], merge_intervals([[1,4],[4,5]]))

    def test_3(self):
        self.assertEqual([[0, 100]], merge_intervals([[i, i+1] for i in range(0, 100)]))

    def test_4(self):
        self.assertEqual([[0, 1000000]], merge_intervals([[i, i+1] for i in range(0, 10**6)]))

    def test_5(self):
        self.assertEqual(
            [[i, i+1] for i in range(0, 10**6, 2)],
            merge_intervals([[i, i+1] for i in range(0, 10**6, 2)])
        )

    def test_6(self):
        self.assertEqual([[0, 1000000]], merge_intervals([[0, 1000000]] * 10**6))

if __name__ == "__main__":
    unittest.main()

Why Sorting Makes All the Difference

Sorting by the start time ensures:

    • Every pair only needs to be compared with the previous merged interval
    • We never backtrack or recheck old intervals

This alone drops the runtime from quadratic to logarithmic scale.

Ready to Level Up?

Mastering Merge Intervals is not just about solving one problem — it’s about learning to spot opportunities to simplify problems with sorting. 

This strategy appears in sweep line algorithms, meeting room schedulers, and more.

Keep testing and refactoring. Try re-implementing the brute-force version to reinforce your understanding. Then, go build your animation of how the algorithm works!

If you're looking for the best structured learning in Python, follow us at PythonHaven.