ToolMight LogoToolMight
MediumArrays & HashingPattern: Interval SortingPattern: Greedy Overlap Merging

Merge Intervals

Merge all overlapping intervals and return an array of non-overlapping intervals that cover all inputs. The definitive problem for mastering interval scheduling and sorting by start time.

Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Examples & Constraints

Example 1
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].
Example 2
Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: Intervals [1, 4] and [4, 5] touch at 4, so they are considered overlapping.
Constraints
  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4

Sort by Start Time & Greedy Merge

Optimal Approach
Time:O(n log n)
Space:O(n)

Sort intervals in ascending order by start time. Iterate through intervals: if the current interval starts before or at the previous end time, merge them by extending the end boundary.

Time ComplexityO(n log n)

Dominated by sorting the N intervals by start time. The subsequent linear merging pass takes O(n). Total runtime is O(n log n).

Space ComplexityO(n)

Consumes space to store the merged output list of intervals (and auxiliary sorting memory).

Underlying algorithmic logic

The Invariant: Chronological Start Times

When intervals are unsorted, determining whether two segments collide requires an expensive O(n²) comparison across all pairs.

However, if we sort intervals by their start time (start_i):

  • Any interval that can possibly overlap with interval A must appear directly after A in the sorted list!

The Greedy Merging Rule:

  1. Sort intervals such that intervals[i][0] <= intervals[i + 1][0].
  2. Initialize a merged list res and append the first interval: res.append(intervals[0]).
  3. For each subsequent interval curr in intervals[1..n-1]:
  • Let last be the most recently added interval in res.
  • Case 1: Overlap: If curr.start <= last.end:
  • The intervals collide!
  • Merge them by taking the maximum end boundary: last.end = max(last.end, curr.end)
  • Case 2: No Overlap: If curr.start > last.end:
  • There is a gap between last and curr.
  • curr starts a brand new independent interval!
  • Append curr to res.
  1. Return res.

Step-by-step execution walkthrough

1
Sorted Input

[[1, 3], [2, 6], [8, 10], [15, 18]]. Insert [1, 3] into merged list.

merged = [[1, 3]]
2
Inspect [2, 6]

2 <= 3 (overlap!). Merge: end = max(3, 6) = 6. Update last interval to [1, 6].

merged = [[1, 6]]
3
Inspect [8, 10]

8 > 6 (no overlap!). Append [8, 10] as new interval.

merged = [[1, 6], [8, 10]]
4
Inspect [15, 18]

15 > 10 (no overlap!). Append [15, 18]. Finished.

merged = [[1, 6], [8, 10], [15, 18]]
Advantages
  • •Optimal O(n log n) runtime
  • •Clean single-pass scan after sorting by start time
Trade-offs
  • •Mutates original ordering by requiring a start-time sort

Code Implementations

Copy & paste production-ready solutions for Sort by Start Time & Greedy Merge in your language of choice

File: solution.py
Python
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    return merged
if __name__ == "__main__":
    test1 = [[1, 3], [2, 6], [8, 10], [15, 18]]
    test2 = [[1, 4], [4, 5]]
    print("test1 merged:", merge_intervals(test1))
    print("test2 merged:", merge_intervals(test2))
Interactive visualizer available

Understand Array & Matrix Visually

Explore sequential element access, subsegment manipulations, insertion, deletion, and 2D grid matrix walks. Test live edge cases and watch memory state transitions step-by-step.

Launch Array & Matrix Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
MediumTwo Pointers
Visualizer

3Sum

Find all unique triplets in an array that sum up to zero. The premier problem for learning how to combine sorting with two-pointer inward scans to avoid cubic brute force.

1 approach(O(n²))
Learn logic
EasyArrays & Hashing
Visualizer

Contains Duplicate

Determine if any value appears at least twice in an integer array. A foundational problem for mastering constant-time hash lookups vs sorting trade-offs.

2 approaches(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic