Merge Overlapping Intervals

Tags

Merge Overlapping Intervals

Category

Arrays

Difficulty

Medium

Problem Statement

Given an array of intervals where each interval is a pair [start, end], merge all overlapping intervals and return the resulting array of non-overlapping intervals.

Intuition

If we sort intervals by their start value, overlapping intervals become adjacent. We can then sweep through the sorted list and greedily merge each interval into the current one if they overlap, or start a new interval if they do not.

Approach

  1. Sort the intervals by their start value.
  2. Initialize a result list with the first interval.
  3. For each subsequent interval:
    • Let currentInterval be the last interval in the result list.
    • If the current interval's start is less than or equal to currentInterval's end, they overlap. Update currentInterval's end to max(currentInterval.end, interval.end).
    • Otherwise, append the current interval to the result list.
  4. Return the result list.

Pseudocode

function mergeOverlappingIntervals(intervals):
    sort intervals by start value

    merged = [intervals[0]]

    for i from 1 to length(intervals) - 1:
        currentInterval = merged[last]
        nextInterval = intervals[i]

        if nextInterval.start <= currentInterval.end:
            currentInterval.end = max(currentInterval.end, nextInterval.end)
        else:
            merged.append(nextInterval)

    return merged

Time & Space Complexity

  • Time: O(n log n) — dominated by the sorting step. The merge sweep is O(n).
  • Space: O(n) — for the result list in the worst case where no intervals overlap.

Key Insights

  • Sorting is the key enabler: it guarantees that if interval B overlaps with interval A, B immediately follows A (or is part of a chain following A).
  • When merging, always take the maximum of the two end values — a later-starting interval can still extend further.
  • This greedy approach is optimal; no better worst-case time complexity is possible since we must at least read all intervals.

Edge Cases

  • Single interval: return it as-is.
  • No overlapping intervals: return the sorted list unchanged.
  • All intervals overlap into one: return a single merged interval.
  • Intervals that share only an endpoint (e.g., [1,3] and [3,5]): these are considered overlapping and should be merged to [1,5].
  • Intervals are already sorted: the algorithm still works correctly.
  • Nested intervals (e.g., [1,10] and [3,5]): the larger interval absorbs the smaller one.

Linked mentions