How do you solve Merge Intervals?

Sort the intervals by their start times. Initialize the output list with the first interval. Iterate through the remaining intervals, and for each, check if it overlaps with the last interval in the output. If it does, merge by updating the end to the maximum of both ends. If not, append the current interval to the output. This approach runs in O(n log n) due to sorting and O(n) for merging.

Merge Intervals

Q: What is the time complexity of Merge Intervals?

O(n log n). Sorting the intervals dominates the runtime with O(n log n). The subsequent single pass to merge intervals is O(n), which does not increase the overall complexity.

Q: What pattern does Merge Intervals use?

The Pattern: Merge Intervals (Sorting and Linear Merge) The Heuristic: Sorting intervals by start time aligns all overlapping intervals consecutively, enabling a single linear pass to merge by comparing current interval start with the last merged interval end, thus reducing a complex pairwise overlap problem to a simple linear scan.

Medium Merge Intervals

Problem

Given a collection of intervals, merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

1 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ start_i ≤ end_i ≤ 10⁴

Example

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

Output: [[1,6],[8,10],[15,18]]

The intervals [1,3] and [2,6] overlap because 2 <= 3. Merging them results in [1,6]. The other intervals do not overlap with this merged interval or each other, so they remain unchanged. The final output is [[1,6],[8,10],[15,18]].

Approach

Straightforward Solution

A brute-force approach would compare every interval with every other interval to check for overlaps, resulting in O(n^2) time complexity, which is inefficient for large inputs.

Core Observation

Overlapping intervals can be merged if they share any common range. Sorting intervals by their start times places all potentially overlapping intervals consecutively, enabling a linear scan to merge them efficiently.

Path to Optimal

Preview

Sorting intervals by their start times ensures that any overlapping intervals appear next to each other. This allows a single pass through the sorted list to merge intervals by comparing the current interval's start with the last merged interval's end…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort the intervals by their start times. Initialize the output list with the first interval…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log n)

Sorting the intervals dominates the runtime with O(n log n). The subsequent single pass to merge intervals is O(n), which does not increase the overall complexity.

Space

O(n)

The output list stores merged intervals and can be as large as the input in the worst case (no overlaps). The sorting operation may also require O(n) space depending on the sorting algorithm used.

Pattern Spotlight

Merge Intervals (Sorting and Linear Merge)

Sorting intervals by start time aligns all overlapping intervals consecutively, enabling a single linear pass to merge by comparing current interval start with the last merged interval end, thus reducing a complex pairwise overlap problem to a simple linear scan.

Solution

Python

1class Solution:
  def merge(self, intervals: list[list[int]]) -> list[list[int]]:
      intervals.sort(key = lambda i : i[0])
      output = [intervals[0]]
5
      for start, end in intervals[1:]:
          last_end = output[-1][1]
8
          if start <= last_end:
              output[-1][1] = max(last_end, end)
          else:
              output.append([start, end])
      
      return output

Step-by-Step Solution

Sort Intervals by Start Time to Align Overlaps

3	`intervals.sort(key = lambda i : i[0])`

Objective

To arrange intervals so that any overlapping intervals appear consecutively, enabling efficient merging.

Key Insight

Sorting by the start time is the foundational step that transforms the problem from a complex pairwise overlap check into a linear scan. This ordering guarantees that when iterating, any interval that overlaps with the previous merged interval will be adjacent, allowing immediate detection and merging.

Interview Quick-Check

Core Logic

Sorting intervals by their start times ensures that all overlapping intervals are grouped together, enabling a linear merge.

Common Pitfalls & Bugs

Failing to sort intervals first can cause missed overlaps or incorrect merges, as intervals may appear out of order.

Initialize Merged List with First Interval

To start the merged intervals list with the earliest interval as a baseline for subsequent merges.

Iterate Through Intervals and Merge Overlaps

To scan through the sorted intervals and merge any that overlap with the last merged interval.

Return the List of Merged Intervals

To output the final merged intervals after processing all input intervals.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 9 Critical

if start <= last_end:

Check if the current interval overlaps with the last merged interval.

This condition detects overlap by verifying if the current interval's start is less than or equal to the last merged interval's end, which is the key to deciding whether to merge.

Line 3 Critical

intervals.sort(key = lambda i : i[0])

Sort the intervals by their start times in ascending order.

Sorting aligns all intervals so that overlapping intervals are adjacent, enabling a single linear pass to merge them efficiently.

Line 10 Critical

output[-1][1] = max(last_end, end)

Merge the current interval by updating the last merged interval's end.

Updating the end to the maximum of both intervals ensures the merged interval covers the entire overlapping range, preserving correctness.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why is sorting intervals by their start time critical before merging?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Merge Intervals from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Merge Intervals drill

or drill a free problem

1	`class Solution:`
2	`def merge(self, intervals: list[list[int]]) -> list[list[int]]:`
3	`intervals.sort(key = lambda i : i[0])`
4	`output = [intervals[0]]`
5
6	`for start, end in intervals[1:]:`
7	`last_end = output[-1][1]`
8
9	`if start <= last_end:`
10	`output[-1][1] = max(last_end, end)`
11	`else:`
12	`output.append([start, end])`
13
14	`return output`