Merge intervals: combine overlapping ranges efficiently

You're sitting across from a Facebook interviewer who slides a whiteboard marker your way. "We have a list of meeting room bookings," they say, "and some overlap. Can you consolidate them into the fewest non-overlapping time slots?" This is the classic merge intervals problem, also known as "Merge Intervals" on LeetCode and other platforms. It tests your ability to combine sorting with greedy logic, and it shows up constantly at companies like Facebook, Amazon, and Bloomberg.

TL;DR

Sort the intervals by their start values, then walk through them left to right. For each interval, if it overlaps with the last merged interval (the previous end is greater than or equal to the current start), extend the merged interval's end to the maximum of both ends. Otherwise, add the interval as-is. This runs in O(n log n) time due to sorting and uses O(n) space for the result.

Why This Problem Matters

Merge intervals is one of those problems that sits at the intersection of sorting, greedy algorithms, and interval arithmetic. It's a mid-level problem that interviewers love because it reveals how you think about ordering, edge cases, and in-place modifications. The pattern you learn here transfers directly to related problems like insert interval, meeting rooms, and interval list intersections.

Understanding the Problem

Given a list of intervals where each interval is a pair [start, end], merge all overlapping intervals and return a sorted list of non-overlapping intervals that cover all the ranges in the input.

Here's our primary example:

mergeIntervals([[1,3],[2,6],[8,10],[15,18]]) -> [[1,6],[8,10],[15,18]]

Notice that [1,3] and [2,6] overlap because 3 ≥ 2, so they merge into [1,6]. The other two intervals don't overlap with anything, so they stay as-is.

More examples:

mergeIntervals([[1,3],[2,9]])           -> [[1,9]]
mergeIntervals([[-1,3],[1,2],[2,4]])    -> [[-1,4]]
mergeIntervals([[0,1],[0,1],[0,1],[0,0]]) -> [[0,1]]

Constraints

• All intervals are pairs of length 2.
• The input list contains between 1 and 10,000 intervals.
• interval[0] ≤ interval[1] for every interval.
• Values range from -10,000 to 10,000.
• The output should be sorted in ascending order.

Edge Cases to Consider

1. Single interval: Already merged, return as-is.
2. All intervals overlap: Everything collapses into one interval.
3. No intervals overlap: Return the sorted input unchanged.
4. Touching endpoints: [1,3] and [3,5] should merge to [1,5].
5. Duplicate intervals: [0,1],[0,1],[0,1] merge to [0,1].
6. Negative values: The algorithm works identically with negative numbers.

Solution Approach

The brute-force method would compare every interval against every other interval, but that gives us O(n^2) time. We can do better.

The Key Insight

If the intervals are sorted by start value, overlapping intervals are guaranteed to be adjacent. This means we only need to compare each interval with the one immediately before it. Sorting transforms a complex clustering problem into a simple linear scan.

Building the Algorithm

1. Sort the intervals by their start values.
2. Initialize an empty result list.
3. Iterate through the sorted intervals:
   • If the result list is empty or the current interval doesn't overlap with the last merged interval, add it to the result.
   • If it does overlap, extend the last merged interval's end to the maximum of both ends.
4. Return the result list.

Here's how the overlap detection works:

Two intervals overlap when the end of the last merged interval is greater than or equal to the start of the current interval. When they overlap, we keep the larger end value.

Walking Through the Example

Let's trace through [[1,3],[2,6],[8,10],[15,18]] step by step:

The intervals are already sorted in this case. We add [1,3] to an empty result. Then [2,6] overlaps because 3 >= 2, so we extend to [1,6]. Next, [8,10] doesn't overlap because 6 < 8, so we add it as a new interval. Finally, [15,18] doesn't overlap because 10 < 15, and we add it too.

Result: [[1,6],[8,10],[15,18]].

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class Solution {
  public List<List<Integer>> mergeIntervals(List<List<Integer>> intervals) {
    // Sort intervals by start value
    List<List<Integer>> sortedIntervals =
      intervals
        .stream()
        .sorted(Comparator.comparingInt(i -> i.get(0)))
        .collect(Collectors.toList());

    // Create output list for merged intervals
    LinkedList<List<Integer>> merged = new LinkedList<>();

    // Iterate through sorted intervals
    for (List<Integer> interval : sortedIntervals) {
      // If merged is empty or no overlap, add the interval
      if (merged.isEmpty() || merged.getLast().get(1) < interval.get(0)) {
        merged.add(interval);
      } else {
        // Merge by extending the last interval's end
        merged.getLast().set(1, Math.max(merged.getLast().get(1), interval.get(1)));
      }
    }

    return merged;
  }
}

A few things to notice about this implementation:

• We use LinkedList for the result because getLast() gives us O(1) access to the most recently added interval. An ArrayList would work too, but you'd index with merged.get(merged.size() - 1).
• The stream-based sort creates a new sorted list rather than modifying the input. This is a clean functional style, though sorting in-place would save memory.
• The merge condition merged.getLast().get(1) < interval.get(0) checks strict less-than. When endpoints are equal (like [1,3] and [3,5]), the condition is false, so they correctly merge.

Chain Merges

One subtle behavior worth understanding is how chain merges work. Consider this input:

Each adjacent pair shares an endpoint. The algorithm handles this naturally because it always compares against the last merged interval, not the original input. After merging [1,2] and [2,3] into [1,3], the next comparison is between [1,3] and [3,4], which also merges. This cascading effect produces [1,5] without any special logic.

Negative Values

The algorithm handles negative values without any changes:

The comparison operators work identically regardless of sign. Sorting [-5,-3] and [-4,-2] keeps them in the right order, and -3 >= -4 correctly identifies the overlap.

Complexity Analysis

Time Complexity: O(n log n)

The sorting step dominates at O(n log n). The merge scan afterward is a single pass through the sorted list, which is O(n). Combined: O(n log n).

You might wonder if we can do better. We can't, at least not with comparison-based sorting. Any algorithm that needs to determine ordering relationships between intervals requires at least O(n log n) comparisons in the worst case.

Space Complexity: O(n)

The result list can hold up to n intervals when none overlap. The Java stream-based sort also creates a copy of the input, adding another O(n). If you sort in-place and exclude the output from the space analysis, auxiliary space drops to O(1).

Common Pitfalls

1. Forgetting to sort: Without sorting, you'd miss overlaps between non-adjacent intervals. Input [[8,10],[1,3],[2,6]] would fail without sorting because [1,3] and [2,6] aren't adjacent.

2. Wrong merge condition: Using <= instead of < in the overlap check would prevent merging intervals that share an endpoint. [1,3] and [3,5] should merge, but merged.getLast().get(1) <= interval.get(0) would add them separately.

3. Replacing instead of extending: When merging, you must take Math.max(lastEnd, currentEnd), not just use the current interval's end. With [1,9] and [2,6], the merged interval should be [1,9], not [1,6].

4. Modifying the input list: Some languages pass arrays by reference. Sorting in-place is fine, but be aware that you're mutating the caller's data.

Interview Tips

When solving this in an interview:

1. Start with the insight: "If I sort by start value, overlapping intervals become adjacent, which lets me solve this in a single pass."

2. Discuss the data structure choice: Mention why LinkedList (or your language's equivalent) gives convenient access to the last element.

3. Walk through an example: Trace [[1,3],[2,6],[8,10],[15,18]] step by step, showing how the merge condition works at each step.

4. Cover edge cases: Mention single-element input, all-overlapping intervals, touching endpoints, and negative values.

5. Know the follow-ups: Be ready for "What if the intervals are already sorted?" (skip the sort, O(n) time), "What if you need to insert a new interval?" (the insert interval problem), or "How would you count the minimum meeting rooms needed?" (the meeting rooms problem).

Key Takeaways

• Sorting by start value is the foundation of most interval problems. It reduces overlap detection from an all-pairs comparison to a linear scan.
• The merge condition checks strict less-than (lastEnd < currentStart) so that touching endpoints like [1,3] and [3,5] correctly merge.
• Always extend using Math.max(lastEnd, currentEnd) when merging. The current interval's end is not always larger, as in [1,9] merged with [2,6].
• Chain merges happen naturally because the algorithm always compares against the last merged interval, not the original input.
• The O(n log n) time complexity is optimal for this problem since comparison-based sorting has an O(n log n) lower bound.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def merge_intervals(self, intervals: List[List[int]]) -> List[List[int]]:
        sorted_intervals = sorted(intervals, key=lambda l: l[0])
        merged = []
        for interval in sorted_intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

JavaScript

class Solution {
  mergeIntervals(intervals) {
    const sortedIntervals = intervals.sort((l1, l2) => l1[0] - l2[0]);
    const merged = [];
    sortedIntervals.forEach(interval => {
      if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
        merged.push(interval);
      } else {
        merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
      }
    });
    return merged;
  }
}

TypeScript

class Solution {
  mergeIntervals(intervals: number[][]): number[][] {
    const sortedIntervals = intervals.sort((l1, l2) => l1[0] - l2[0]);
    const merged: number[][] = [];
    for (const interval of sortedIntervals) {
      if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
        merged.push(interval);
      } else {
        merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
      }
    }
    return merged;
  }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
  std::vector<std::vector<int>> mergeIntervals(std::vector<std::vector<int>> intervals) {
    std::sort(intervals.begin(), intervals.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
      return a[0] < b[0];
    });

    std::vector<std::vector<int>> merged;

    for (const std::vector<int> &interval: intervals) {
      if (merged.empty() || merged.back()[1] < interval[0]) {
        merged.push_back(interval);
      } else {
        merged.back()[1] = std::max(merged.back()[1], interval[1]);
      }
    }
    return merged;
  }
};

Go

package solution

import "sort"

func (s *Solution) MergeIntervals(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	var merged [][]int

	for _, interval := range intervals {
		if len(merged) == 0 || merged[len(merged)-1][1] < interval[0] {
			merged = append(merged, interval)
		} else {
			if merged[len(merged)-1][1] < interval[1] {
				merged[len(merged)-1][1] = interval[1]
			}
		}
	}
	return merged
}

Scala

import scala.collection.mutable

class Solution {
  def mergeIntervals(intervals: List[List[Int]]): List[List[Int]] = {
    val sortedIntervals = intervals.sortWith(_.head < _.head)
    val merged = mutable.ArrayDeque[List[Int]]()
    for (interval <- sortedIntervals) {
      if (merged.isEmpty || merged.last(1) < interval.head) merged.append(interval)
      else {
        val lastInterval = merged.removeLast()
        merged.append(List(lastInterval.head, Math.max(lastInterval(1), interval(1))))
      }
    }
    merged.toList
  }
}

Kotlin

class Solution {
  fun mergeIntervals(intervals: List<List<Int>>): List<List<Int>> {
    val sortedIntervals = intervals.sortedBy { it[0] }
    val merged = mutableListOf<MutableList<Int>>()

    for (interval in sortedIntervals) {
      if (merged.isEmpty() || merged.last()[1] < interval[0]) {
        merged.add(interval.toMutableList())
      } else {
        merged.last()[1] = maxOf(merged.last()[1], interval[1])
      }
    }
    return merged
  }
}

Swift

import Foundation

class Solution {
    func mergeIntervals(_ intervals: [[Int]]) -> [[Int]] {
        let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
        var merged: [[Int]] = []

        for interval in sortedIntervals {
            if merged.isEmpty || merged[merged.count - 1][1] < interval[0] {
                merged.append(interval)
            } else {
                merged[merged.count - 1][1] = max(merged[merged.count - 1][1], interval[1])
            }
        }
        return merged
    }
}

Ruby

class Solution
  def merge_intervals(intervals)
    sorted_intervals = intervals.sort_by { |interval| interval[0] }
    merged = []

    sorted_intervals.each do |interval|
      if merged.empty? || merged.last[1] < interval[0]
        merged << interval
      else
        merged.last[1] = [merged.last[1], interval[1]].max
      end
    end
    merged
  end
end

Rust

pub struct Solution;

impl Solution {
    pub fn merge_intervals(&self, mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        intervals.sort_by_key(|interval| interval[0]);
        let mut merged: Vec<Vec<i32>> = Vec::new();

        for interval in &intervals {
            if merged.is_empty() || merged.last().unwrap()[1] < interval[0] {
                merged.push(interval.clone());
            } else {
                merged.last_mut().unwrap()[1] = merged.last().unwrap()[1].max(interval[1]);
            }
        }
        merged
    }
}

Dart

import 'dart:math';

class Solution {
  List<List<int>> mergeIntervals(List<List<int>> intervals) {
    intervals.sort((a, b) => a[0].compareTo(b[0]));
    List<List<int>> merged = [];

    for (List<int> interval in intervals) {
      if (merged.isEmpty || merged.last[1] < interval[0]) {
        merged.add(interval);
      } else {
        merged.last[1] = max(merged.last[1], interval[1]);
      }
    }
    return merged;
  }
}

C#

public class Solution {
    public List<List<int>> MergeIntervals(List<List<int>> intervals) {
        var sortedIntervals = intervals.OrderBy(i => i[0]).ToList();
        var merged = new List<List<int>>();

        foreach (var interval in sortedIntervals) {
            if (merged.Count == 0 || merged[^1][1] < interval[0]) {
                merged.Add(interval);
            } else {
                merged[^1][1] = Math.Max(merged[^1][1], interval[1]);
            }
        }
        return merged;
    }
}

PHP

<?php

class Solution {
    public function mergeIntervals(array $intervals): array {
        usort($intervals, fn($a, $b) => $a[0] - $b[0]);
        $merged = [];

        foreach ($intervals as $interval) {
            if (empty($merged) || $merged[count($merged) - 1][1] < $interval[0]) {
                $merged[] = $interval;
            } else {
                $merged[count($merged) - 1][1] = max($merged[count($merged) - 1][1], $interval[1]);
            }
        }
        return $merged;
    }
}

Practice Makes Perfect

Once you've nailed merge intervals, these related problems build on the same interval reasoning:

• Insert interval - Add a new interval to a sorted, non-overlapping list and merge as needed.
• Meeting rooms - Determine if a person can attend all meetings given a list of time intervals.
• Interval list intersections - Find the intersection of two lists of intervals.
• Non-overlapping intervals - Find the minimum number of intervals to remove so the rest don't overlap.

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. The interval pattern you just learned shows up in system design too, from calendar scheduling to database query optimization. Practice it until the sort-then-scan approach feels automatic.