← Back to DevBytes
Developer Tutorial July 16, 2026 16 min read

Merge Intervals: Multiple Solutions and Complexity Analysis

Introduction to the Merge Intervals Problem

The Merge Intervals problem is one of the most fundamental and frequently encountered algorithmic challenges in software engineering. At its core, it asks you to take a collection of intervals—each defined by a start and end point—and produce a new set where all overlapping intervals have been combined into contiguous blocks. This problem appears constantly in coding interviews, production systems, and anywhere that involves scheduling, time-range management, or spatial coordinate merging.

What makes this problem particularly instructive is that it sits at the intersection of sorting, greedy algorithms, and data structure design. The optimal solution is elegant and surprisingly simple once you understand the key insight: sort first, then merge in a single pass. But there are multiple valid approaches, each with different trade-offs in terms of time complexity, space complexity, and adaptability to real-world constraints like streaming data or immutability requirements.

Problem Statement and Formal Definition

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

Given a collection of intervals where each interval is represented as [start, end] with start ≤ end, merge all overlapping intervals and return a new array of non-overlapping intervals that cover all the same ranges.

Overlapping condition: Two intervals [a_start, a_end] and [b_start, b_end] overlap if a_start ≤ b_end AND b_start ≤ a_end (assuming we merge intervals that touch at a point, which is the most common convention—always clarify this with your interviewer or in your specs).

Example Scenarios

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

Input:  [[1,4], [4,5]]
Output: [[1,5]]   // if touching intervals merge; otherwise [[1,4],[4,5]]

Input:  [[1,4], [0,2], [3,5]]
Output: [[0,5]]   // after sorting, everything cascades into one interval

Input:  []
Output: []

Input:  [[5,7]]
Output: [[5,7]]   // single interval, no merging needed

Why Merge Intervals Matters: Real-World Applications

This isn't just an abstract puzzle. The merge intervals pattern powers numerous production systems:

Solution 1: Sorting + Linear Scan (Optimal Greedy Approach)

This is the canonical solution and the one you should reach for first. The algorithm has two phases:

Algorithm Steps

  1. Sort all intervals by their start value in ascending order. If two intervals share the same start, sort by end value (though this is often unnecessary for correctness).
  2. Initialize a result list with the first interval (or empty if input is empty).
  3. Iterate through the remaining intervals. For each interval, compare it against the last interval in the result list:
    • If the current interval's start ≤ the last result interval's end → they overlap. Merge by extending the last result interval's end to max(last.end, current.end).
    • Otherwise, they are disjoint. Append the current interval as a new entry in the result list.

Why Sorting First Is Necessary

Without sorting, you'd need to compare every interval against every other interval, leading to O(n²) time. Sorting brings all potentially overlapping intervals adjacent to each other, guaranteeing that once you've placed an interval in the result and moved past it, no future interval can overlap with it (since all future intervals have larger start values, and if they overlapped, they would have been merged already).

Complete Python Implementation

from typing import List

def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
    """
    Merges all overlapping intervals in a list and returns 
    a list of non-overlapping intervals in sorted order.
    
    Time Complexity: O(n log n) — dominated by sorting
    Space Complexity: O(n) for the result list (or O(1) 
    additional if we don't count the output)
    """
    # Handle empty input edge case
    if not intervals:
        return []
    
    # Sort by interval start; if starts are equal, 
    # sort by end to keep processing predictable
    intervals.sort(key=lambda x: (x[0], x[1]))
    
    # Seed the result with the first interval
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        
        # Overlap check: current start <= last end
        if current[0] <= last[1]:
            # Merge: extend the last interval's end
            # to the maximum of both ends
            last[1] = max(last[1], current[1])
        else:
            # Disjoint: append as a new interval
            merged.append(current)
    
    return merged


# ---------- Test Cases ----------
if __name__ == "__main__":
    test_cases = [
        ([[1,3],[2,6],[8,10],[15,18]], [[1,6],[8,10],[15,18]]),
        ([[1,4],[4,5]], [[1,5]]),
        ([[1,4],[0,2],[3,5]], [[0,5]]),
        ([], []),
        ([[5,7]], [[5,7]]),
        ([[1,4],[2,3],[3,5]], [[1,5]]),  # nested intervals
        ([[1,10],[2,3],[4,5],[6,7],[8,9]], [[1,10]]),
    ]
    
    for intervals, expected in test_cases:
        result = merge_intervals(intervals)
        status = "✓" if result == expected else "✗"
        print(f"{status} Input: {intervals}")
        print(f"  Expected: {expected}")
        print(f"  Got:      {result}\n")

In-Place Variation (Modifying Input Array)

If you're allowed to mutate the input and want to avoid allocating extra space for the result (beyond what's needed for the final output), you can merge directly into the sorted array using a write pointer:

def merge_intervals_inplace(intervals: List[List[int]]) -> List[List[int]]:
    """
    Merges intervals in-place after sorting.
    Returns the merged intervals using the same list reference.
    
    Space Complexity: O(1) extra (excluding sorting overhead)
    """
    if not intervals:
        return []
    
    # Sort in-place
    intervals.sort(key=lambda x: (x[0], x[1]))
    
    # write_idx points to the last "kept" interval
    write_idx = 0
    
    for read_idx in range(1, len(intervals)):
        current = intervals[read_idx]
        last = intervals[write_idx]
        
        if current[0] <= last[1]:
            # Overlap: merge into the last kept interval
            last[1] = max(last[1], current[1])
        else:
            # Disjoint: advance write pointer and copy
            write_idx += 1
            intervals[write_idx] = current
    
    # Trim the list to only the kept elements
    # (or return a slice)
    return intervals[:write_idx + 1]

Solution 2: Using a Stack (Explicit Overlap Resolution)

While essentially equivalent to the linear scan approach, explicitly using a stack can make the merge logic more transparent, especially when you need to handle complex overlap semantics (like partial overlaps, splitting intervals, or merging with constraints).

def merge_intervals_stack(intervals: List[List[int]]) -> List[List[int]]:
    """
    Stack-based merge. We sort, then push/pop from a stack
    to resolve overlaps explicitly.
    
    This approach is useful when you need to maintain 
    intermediate state or apply custom merge policies.
    """
    if not intervals:
        return []
    
    intervals.sort(key=lambda x: (x[0], x[1]))
    stack = [intervals[0]]
    
    for current in intervals[1:]:
        top = stack[-1]
        
        if current[0] <= top[1]:
            # Pop the top, merge, and push back
            stack.pop()
            merged = [top[0], max(top[1], current[1])]
            stack.append(merged)
        else:
            stack.append(current)
    
    return stack

The stack approach shines when your merge logic becomes more complex. For instance, if you need to track which original intervals contributed to a merged interval (for audit trails), you can push metadata alongside each interval onto the stack.

Solution 3: Handling Unsorted Streaming Data with a Balanced BST

In production systems, intervals often arrive as a stream and you need to maintain a continuously merged view. Sorting every time new data arrives is inefficient. Instead, you can maintain the merged state in a balanced binary search tree (like a TreeMap in Java or a sortedcontainers library in Python) keyed by start time, and insert each new interval with on-the-fly merging.

Algorithm for Streaming Inserts

  1. For each new interval, find its insertion point in the sorted collection of existing merged intervals.
  2. Identify all existing intervals that overlap with the new interval (these will be contiguous in the sorted order).
  3. Remove those overlapping intervals and insert a single merged interval spanning from the minimum start to the maximum end among all affected intervals.
import bisect

class StreamingIntervalMerger:
    """
    Maintains a sorted, merged list of intervals that 
    supports efficient insertion of new intervals one at a time.
    
    Uses Python's bisect module for O(log n) find + O(k) merge
    where k is the number of overlapping intervals removed.
    """
    
    def __init__(self):
        self.intervals = []  # always kept sorted and merged
    
    def add_interval(self, start: int, end: int) -> None:
        new_interval = [start, end]
        
        # Find where this interval would be inserted
        # bisect_left gives the first index where start >= existing start
        i = bisect.bisect_left(
            [iv[0] for iv in self.intervals], start
        )
        
        # Also check the interval just before the insertion point
        # because it might overlap with our new interval
        if i > 0 and self.intervals[i - 1][1] >= start:
            i -= 1
        
        # Collect all overlapping intervals starting from index i
        to_merge = []
        merge_start = start
        merge_end = end
        
        j = i
        while j < len(self.intervals) and self.intervals[j][0] <= merge_end:
            merge_start = min(merge_start, self.intervals[j][0])
            merge_end = max(merge_end, self.intervals[j][1])
            j += 1
        
        # Remove the overlapping range [i:j] and insert the merged one
        self.intervals[i:j] = [[merge_start, merge_end]]
    
    def get_merged(self) -> List[List[int]]:
        return self.intervals


# Example usage
merger = StreamingIntervalMerger()
merger.add_interval(1, 3)
merger.add_interval(2, 6)
merger.add_interval(8, 10)
merger.add_interval(5, 9)   # this bridges [1,6] and [8,10] into [1,10]
print(merger.get_merged())  # Output: [[1, 10]]

This pattern is invaluable for real-time systems like live calendar updates, IoT sensor data aggregation, or network flow monitoring where data arrives continuously and you need instant access to the current merged state.

Solution 4: Functional / Immutable Approach (Map-Reduce Style)

In environments favoring immutability (like React state management, Redux reducers, or functional data pipelines), you may want a pure function without mutation. The sorting + fold pattern works beautifully:

from functools import reduce

def merge_intervals_functional(intervals: List[List[int]]) -> List[List[int]]:
    """
    Pure functional merge using reduce (fold).
    No mutation — each step produces a new accumulator list.
    """
    if not intervals:
        return []
    
    sorted_intervals = sorted(intervals, key=lambda x: (x[0], x[1]))
    
    def merge_step(acc: List[List[int]], current: List[int]) -> List[List[int]]:
        if not acc:
            return [current]
        
        last = acc[-1]
        if current[0] <= last[1]:
            # Return new list with last element replaced by merged interval
            return acc[:-1] + [[last[0], max(last[1], current[1])]]
        else:
            return acc + [current]
    
    return reduce(merge_step, sorted_intervals, [])

# This version is well-suited for frameworks like React/Redux
# where state must be replaced, not mutated.

Complexity Analysis Across All Solutions

Understanding the trade-offs is critical for choosing the right approach in different contexts:

Time Complexity

Approach Initial Setup Per-Insert / Query Total for n intervals
Sort + Scan O(n log n) sort N/A (batch) O(n log n)
Stack-Based O(n log n) sort N/A (batch) O(n log n)
Streaming BST O(1) empty O(k + log n) where k = overlapping count O(n log n) if all inserted; amortized better for sparse overlaps
Functional Reduce O(n log n) sort N/A (batch) O(n log n) with O(n²) worst-case list concatenation overhead
Brute Force (all-pairs) O(1) N/A O(n²) — avoid for production

Space Complexity

When to Use Each Approach

Edge Cases and Common Pitfalls

1. Touching vs. Overlapping Intervals

The most common point of confusion is whether intervals that merely touch at a point should be merged. Given [1,4] and [4,5], some definitions treat these as overlapping (because the point 4 is shared), while others treat them as disjoint. Always clarify this upfront. The condition current[0] ≤ last[1] merges touching intervals. Use strict inequality current[0] < last[1] to keep them separate.

# Merging touching intervals (≤)
if current[0] <= last[1]:   # [1,4] and [4,5] → [1,5]

# Keeping touching intervals separate (<)
if current[0] < last[1]:    # [1,4] and [4,5] → two separate intervals

2. Empty Input

Always guard against empty input. The sort + scan approach crashes if you try to seed merged[0] on an empty list. Return an empty list immediately.

3. Single Interval

A single-interval input should be returned as-is (wrapped in a list). The loop simply doesn't execute and the result contains the seed interval.

4. Nested Intervals

Intervals completely contained within others (e.g., [1,10] and [2,5]) must be absorbed correctly. The max(last[1], current[1]) ensures the outer interval's end is preserved. Sorting by start then end ensures the outer interval comes first.

5. Unsorted Input with No Overlaps

If intervals are disjoint and unsorted, sorting still imposes O(n log n) but the scan simply appends each one. This is the best-case post-sort behavior.

6. Large Coordinate Values

Intervals spanning large integer ranges (e.g., [-10^9, 10^9]) don't affect the algorithm's logic but may cause overflow in languages with fixed-size integers if you compute midpoints or differences. The merge algorithm itself only uses comparisons, so it's safe.

Best Practices for Production Code

Putting It All Together: A Production-Ready Implementation

Here is a robust, well-documented implementation suitable for use in real codebases, incorporating all the best practices discussed:

from typing import List, Tuple, Optional
from dataclasses import dataclass
import bisect

@dataclass(frozen=True)
class Interval:
    """Immutable interval representation."""
    start: int
    end: int
    
    def __post_init__(self):
        if self.start > self.end:
            raise ValueError(
                f"Invalid interval: start ({self.start}) > end ({self.end})"
            )
    
    def overlaps_with(self, other: 'Interval', merge_touching: bool = True) -> bool:
        """Check if two intervals overlap."""
        if merge_touching:
            return self.start <= other.end and other.start <= self.end
        else:
            return self.start < other.end and other.start < self.end
    
    def merge_with(self, other: 'Interval') -> 'Interval':
        """Create a new interval spanning both."""
        return Interval(
            start=min(self.start, other.start),
            end=max(self.end, other.end)
        )
    
    def to_list(self) -> List[int]:
        return [self.start, self.end]


def merge_intervals_production(
    intervals: List[Interval],
    merge_touching: bool = True
) -> List[Interval]:
    """
    Production-grade interval merging.
    
    Args:
        intervals: List of Interval objects (may be unsorted, may be empty).
        merge_touching: If True, intervals that touch at a point 
            (e.g., [1,4] and [4,5]) are merged. If False, they remain separate.
    
    Returns:
        A new list of non-overlapping Interval objects in sorted order.
    
    Time:  O(n log n)
    Space: O(n) for the result list
    """
    if not intervals:
        return []
    
    # Sort by start, then by end (descending end for same start 
    # ensures outer intervals come first, simplifying containment)
    sorted_intervals = sorted(
        intervals,
        key=lambda iv: (iv.start, -iv.end)
    )
    
    merged: List[Interval] = [sorted_intervals[0]]
    
    for current in sorted_intervals[1:]:
        last = merged[-1]
        
        if current.overlaps_with(last, merge_touching=merge_touching):
            # Replace the last element with the merged interval
            merged[-1] = last.merge_with(current)
        else:
            merged.append(current)
    
    return merged


# ---------- Comprehensive Tests ----------
def run_tests():
    """Verify correctness across a wide range of cases."""
    
    def iv(start, end):
        return Interval(start, end)
    
    def assert_merged(input_intervals, expected, merge_touching=True):
        result = merge_intervals_production(input_intervals, merge_touching)
        result_lists = [r.to_list() for r in result]
        expected_lists = [e.to_list() for e in expected]
        assert result_lists == expected_lists, \
            f"Failed: {input_intervals} → expected {expected_lists}, got {result_lists}"
        print(f"✓ Test passed")
    
    # Test 1: Classic overlapping case
    assert_merged(
        [iv(1,3), iv(2,6), iv(8,10), iv(15,18)],
        [iv(1,6), iv(8,10), iv(15,18)]
    )
    
    # Test 2: Touching intervals with merge_touching=True
    assert_merged(
        [iv(1,4), iv(4,5)],
        [iv(1,5)],
        merge_touching=True
    )
    
    # Test 3: Touching intervals with merge_touching=False
    assert_merged(
        [iv(1,4), iv(4,5)],
        [iv(1,4), iv(4,5)],
        merge_touching=False
    )
    
    # Test 4: Empty input
    assert_merged([], [])
    
    # Test 5: Single interval
    assert_merged([iv(5,7)], [iv(5,7)])
    
    # Test 6: Nested intervals
    assert_merged(
        [iv(1,10), iv(2,3), iv(4,5), iv(6,7), iv(8,9)],
        [iv(1,10)]
    )
    
    # Test 7: All disjoint
    assert_merged(
        [iv(1,2), iv(4,5), iv(7,8)],
        [iv(1,2), iv(4,5), iv(7,8)]
    )
    
    # Test 8: Unsorted cascading merge
    assert_merged(
        [iv(3,6), iv(1,4), iv(2,5), iv(8,10)],
        [iv(1,6), iv(8,10)]
    )
    
    # Test 9: Negative and positive spans
    assert_merged(
        [iv(-10, -5), iv(-7, 0), iv(1, 3)],
        [iv(-10, 0), iv(1, 3)]
    )
    
    # Test 10: Large values
    assert_merged(
        [iv(-1000000000, 500000000), iv(400000000, 1000000000)],
        [iv(-1000000000, 1000000000)]
    )
    
    print("All tests passed successfully!")

if __name__ == "__main__":
    run_tests()

Variations and Related Problems

Once you master the basic merge intervals pattern, several related problems become approachable with similar techniques:

Each of these variants builds on the core insight: sorting intervals by a strategic key and then walking through them linearly unlocks efficient greedy solutions.

Conclusion

The Merge Intervals problem is deceptively simple yet profoundly useful. Its optimal solution—sorting followed by a single linear scan—is a textbook example of how a preprocessing step can collapse a quadratic problem into linearithmic time. We've explored multiple implementations: the classic sort-and-scan, an in-place variant for memory-constrained environments, a stack-based approach for extensibility, a streaming BST inserter for real-time data, and a functional reduce for immutable state management.

The key takeaways are clear: always sort first (unless your data arrives pre-sorted or you're using a tree structure that maintains order), clarify your overlap semantics (touching vs. strictly overlapping), guard against empty inputs, and choose your implementation style based on your runtime context—batch vs. streaming, mutable vs. immutable, simple vs. extensible.

With the production-ready code and comprehensive test suite provided, you now have a solid foundation to handle interval merging in any real-world scenario. The pattern extends far beyond simple integer ranges—it applies to time spans, spatial coordinates, version ranges, and any domain where overlapping linear segments need consolidation. Master this pattern, and you'll find it recurring throughout your career in countless unexpected places.

🚀 Need a reliable AI agent for your project?

Deploy Hermes Agent in 10 minutes. Managed hosting, zero DevOps.

Get Started — $23.99/mo
← Back to all articles