Combining Overlapping Ranges: merge intervals with sorting

A Meta interviewer slides a list of meeting times across the table: [[1,3],[2,6],[8,10],[15,18]]. "Some of these overlap. Can you merge them into the smallest set of non-overlapping intervals?" This is Combining Overlapping Ranges, also known as Merge Intervals on other platforms. It appears constantly at Meta, Google, Bloomberg, Amazon, and Uber, and it's a staple of the Blind 75 list. The problem tests whether you can recognize that sorting transforms a messy overlap problem into a clean linear scan.

TL;DR

Sort the intervals by start time. Initialize a result list with the first interval. For each remaining interval, check if it overlaps with the last merged interval (does the current end >= the next start?). If yes, merge by extending the end to the maximum of both ends. If no, add the interval to the result as-is. Time: O(n log n) for the sort. Space: O(n) for the output.

The Problem

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

merge([[1,3],[2,6],[8,10],[15,18]]) => [[1,6],[8,10],[15,18]]
merge([[1,4],[4,5]])                => [[1,5]]
merge([[1,4],[0,2],[3,5]])          => [[0,5]]

Two intervals overlap when one starts before the other ends. Intervals that share an endpoint (like [1,4] and [4,5]) are also considered overlapping.

Why Sorting Is the Key

Without sorting, you would have to compare every pair of intervals to find overlaps, resulting in O(n^2) behavior. Sorting by start time changes the problem entirely. Once sorted, overlapping intervals are always adjacent. You only need to compare each interval with the one right before it.

After sorting, the overlap check becomes a simple comparison: does the previous interval's end reach the current interval's start?

The Algorithm

1. Sort intervals by start time.
2. Add the first interval to a merged list.
3. For each remaining interval:
   • If it overlaps with the last interval in merged (i.e., currentEnd >= nextStart), extend the merged interval's end to max(currentEnd, nextEnd).
   • Otherwise, add it as a new entry in merged.
4. Return merged.

Walkthrough: [[1,3],[2,6],[8,10],[15,18]]

The input is already sorted by start time. Here's the merge scan:

First, [1,3] and [2,6] overlap because 3 >= 2, so they merge into [1,6]. Then [1,6] and [8,10] don't overlap (6 < 8), so [8,10] starts a new merged interval. Similarly, [8,10] and [15,18] don't overlap. The final result is [[1,6],[8,10],[15,18]].

Unsorted Input: [[1,4],[0,2],[3,5]]

When the input isn't sorted, the sort step brings everything into order first:

After sorting to [[0,2],[1,4],[3,5]], the scan finds two consecutive overlaps. First [0,2] and [1,4] merge into [0,4], then [0,4] and [3,5] merge into [0,5]. All three intervals collapse into a single range.

Edge Cases

Fully Contained Intervals

When one interval is entirely inside another, the max() operation handles it naturally:

[2,6] and [8,10] are both contained within [1,10]. The merge keeps the larger interval unchanged.

Touching Endpoints

Intervals that share an endpoint are considered overlapping:

The condition 4 >= 4 is true, so [1,4] and [4,5] merge into [1,5]. If the problem required strict overlap (no touching), you would use > instead of >=.

Other Edge Cases

• Single interval: Return it as-is. No merging needed.
• No overlaps: Every interval becomes its own entry in the result. Output equals input.
• All overlapping: Everything collapses into one interval.

Implementation

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

import java.util.*;

public class Solution {
  public int[][] merge(int[][] intervals) {
    if (intervals == null || intervals.length == 0) {
      return new int[0][];
    }

    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

    List<int[]> merged = new ArrayList<>();
    int[] currentInterval = intervals[0];
    merged.add(currentInterval);

    for (int[] interval : intervals) {
      int currentEnd = currentInterval[1];
      int nextStart = interval[0];
      int nextEnd = interval[1];

      if (currentEnd >= nextStart) {
        currentInterval[1] = Math.max(currentEnd, nextEnd);
      } else {
        currentInterval = interval;
        merged.add(currentInterval);
      }
    }

    return merged.toArray(new int[merged.size()][]);
  }
}

A few things to note about the Java implementation:

• Comparator.comparingInt(a -> a[0]) sorts by the first element of each sub-array. This is cleaner than writing a full comparator.
• The currentInterval reference is added to merged early, so when we update currentInterval[1], the change is reflected in the list. This avoids re-indexing into merged on every iteration.
• The loop starts from index 0 (including the first interval), but since the first comparison is with itself, the overlap check is harmlessly true. Some implementations skip index 0 for clarity.

Complexity Analysis

Time: O(n log n)

Sorting dominates at O(n log n). The merge scan is O(n) since each interval is visited exactly once. Total: O(n log n).

You cannot beat O(n log n) for this problem. Without sorted order, there's no way to identify all overlaps in less than O(n^2) time.

Space: O(n)

The output list stores the merged intervals. In the worst case (no overlaps), this is the same size as the input. The sorting step may use O(log n) additional space for its recursive call stack, but O(n) for the output dominates.

Common Mistakes

1. Forgetting to sort. Without sorting, the linear scan misses overlaps between non-adjacent intervals. For example, [[1,4],[5,7],[2,6]] requires sorting to detect that [1,4] and [2,6] overlap.

2. Using > instead of >= for the overlap check. The condition should be currentEnd >= nextStart, not >. Using > misses touching intervals like [1,4] and [4,5].

3. Setting the merged end to nextEnd instead of max(currentEnd, nextEnd). When one interval contains another (e.g., [1,10] and [2,6]), the merged end should stay at 10, not drop to 6. Always use max().

4. Modifying the input array while iterating. Some languages have issues when you sort and then mutate the array during iteration. The safest approach adds intervals to a separate result list.

Interview Tips

• Lead with the sorting insight. "If I sort by start time, overlapping intervals become adjacent, and I can merge in a single pass." This tells the interviewer you see the structure.
• Draw the intervals on a number line. Sketching [1,3] and [2,6] as overlapping segments makes the overlap condition visually obvious.
• State the overlap condition precisely. "Two sorted intervals overlap when the first's end is greater than or equal to the second's start."
• Trace through the max() call. Show why max(currentEnd, nextEnd) is correct for both the partial-overlap and full-containment cases.
• Mention the follow-up. If asked about non-overlapping interval removal or meeting room scheduling, explain how sorting intervals is the common foundation for all interval problems.

Related Problems

Merge Intervals is the foundation for a family of interval-based problems:

• Insert Interval - Insert a new interval into a sorted, non-overlapping list and merge if needed.
• Meeting Rooms - Determine if a person can attend all meetings (check for any overlap).
• Meeting Rooms II - Find the minimum number of conference rooms required (track concurrent overlaps).
• Non-overlapping Intervals - Remove the minimum number of intervals to eliminate all overlaps.
• Interval List Intersections - Find all overlapping segments between two sorted interval lists.

The sort-then-scan pattern from this problem is the starting point for all of them. The only thing that changes is what you do when you detect an overlap.

Ready to practice interval problems? Firecode sequences related problems using spaced repetition so you build intuition for sorting-based patterns over time. Over 50,000 engineers have used it to prepare for interviews at top companies like Meta, Google, and Amazon.

Solutions in Other Languages

Python

from typing import List

class Solution:
    def merge(self, 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 = merged[-1]
            if current[0] <= last_merged[1]:
                last_merged[1] = max(last_merged[1], current[1])
            else:
                merged.append(current)

        return merged

JavaScript

class Solution {
  merge(intervals) {
    if (intervals.length <= 1) return intervals;

    intervals.sort((a, b) => a[0] - b[0]);

    const merged = [];
    let currentInterval = intervals[0];

    for (let i = 1; i < intervals.length; i++) {
      const [currentStart, currentEnd] = currentInterval;
      const [nextStart, nextEnd] = intervals[i];

      if (currentEnd >= nextStart) {
        currentInterval = [currentStart, Math.max(currentEnd, nextEnd)];
      } else {
        merged.push(currentInterval);
        currentInterval = intervals[i];
      }
    }

    merged.push(currentInterval);
    return merged;
  }
}

TypeScript

class Solution {
  merge(intervals: number[][]): number[][] {
    if (intervals.length <= 1) return intervals;

    intervals.sort((a, b) => a[0] - b[0]);

    const merged: number[][] = [];
    let currentInterval = intervals[0];

    for (let i = 1; i < intervals.length; i++) {
      const [currentStart, currentEnd] = currentInterval;
      const [nextStart, nextEnd] = intervals[i];

      if (currentEnd >= nextStart) {
        currentInterval = [currentStart, Math.max(currentEnd, nextEnd)];
      } else {
        merged.push(currentInterval);
        currentInterval = intervals[i];
      }
    }

    merged.push(currentInterval);
    return merged;
  }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  std::vector<std::vector<int>> merge(std::vector<std::vector<int>> &intervals) {
    if (intervals.empty()) return {};

    std::sort(intervals.begin(), intervals.end());

    std::vector<std::vector<int>> merged;
    merged.push_back(intervals[0]);

    for (const auto& interval : intervals) {
      if (merged.back()[1] >= interval[0]) {
        merged.back()[1] = std::max(merged.back()[1], interval[1]);
      } else {
        merged.push_back(interval);
      }
    }

    return merged;
  }
};

Go

import "sort"

func (s *Solution) Merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return [][]int{}
    }

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

    merged := [][]int{}
    currentInterval := intervals[0]

    for _, interval := range intervals {
        if interval[0] <= currentInterval[1] {
            if interval[1] > currentInterval[1] {
                currentInterval[1] = interval[1]
            }
        } else {
            merged = append(merged, currentInterval)
            currentInterval = interval
        }
    }

    merged = append(merged, currentInterval)
    return merged
}

Scala

class Solution {
  def merge(intervals: Array[Array[Int]]): Array[Array[Int]] = {
    if (intervals.isEmpty) return Array.empty[Array[Int]]

    val sortedIntervals = intervals.sortBy(_(0))
    val mergedIntervals = scala.collection.mutable.ArrayBuffer[Array[Int]]()
    var currentInterval = sortedIntervals(0)
    mergedIntervals.append(currentInterval)

    for (i <- 1 until sortedIntervals.length) {
      val nextInterval = sortedIntervals(i)
      val currentEnd = currentInterval(1)

      if (nextInterval(0) <= currentEnd) {
        currentInterval(1) = Math.max(currentEnd, nextInterval(1))
      } else {
        currentInterval = nextInterval
        mergedIntervals.append(currentInterval)
      }
    }

    mergedIntervals.toArray
  }
}

Kotlin

class Solution {
  fun merge(intervals: Array<IntArray>): Array<IntArray> {
    if (intervals.isEmpty()) return emptyArray()

    val sortedIntervals = intervals.sortedBy { it[0] }
    val merged = mutableListOf<IntArray>()
    var currentInterval = sortedIntervals[0]
    merged.add(currentInterval)

    for (interval in sortedIntervals) {
      val currentEnd = currentInterval[1]
      val nextStart = interval[0]
      val nextEnd = interval[1]

      if (currentEnd >= nextStart) {
        currentInterval[1] = maxOf(currentEnd, nextEnd)
      } else {
        currentInterval = interval
        merged.add(currentInterval)
      }
    }

    return merged.toTypedArray()
  }
}

Swift

import Foundation

class Solution {
    func merge(_ intervals: [[Int]]) -> [[Int]] {
        if intervals.isEmpty { return [] }

        let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
        var merged = [sortedIntervals[0]]

        for i in 1..<sortedIntervals.count {
            let currentEnd = merged[merged.count - 1][1]
            let nextStart = sortedIntervals[i][0]
            let nextEnd = sortedIntervals[i][1]

            if currentEnd >= nextStart {
                merged[merged.count - 1][1] = max(currentEnd, nextEnd)
            } else {
                merged.append(sortedIntervals[i])
            }
        }

        return merged
    }
}

Rust

impl Solution {
    pub fn merge(&self, mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        if intervals.is_empty() {
            return Vec::new();
        }

        intervals.sort_by_key(|interval| interval[0]);

        let mut merged: Vec<Vec<i32>> = Vec::new();
        merged.push(intervals[0].clone());

        for interval in &intervals {
            let current_end = merged.last().unwrap()[1];
            let next_start = interval[0];
            let next_end = interval[1];

            if current_end >= next_start {
                merged.last_mut().unwrap()[1] = current_end.max(next_end);
            } else {
                merged.push(interval.clone());
            }
        }

        merged
    }
}

C#

public class Solution {
    public int[][] Merge(int[][] intervals) {
        if (intervals == null || intervals.Length == 0) {
            return Array.Empty<int[]>();
        }

        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

        var merged = new List<int[]>();
        var currentInterval = intervals[0];
        merged.Add(currentInterval);

        foreach (var interval in intervals) {
            var currentEnd = currentInterval[1];
            var nextStart = interval[0];
            var nextEnd = interval[1];

            if (currentEnd >= nextStart) {
                currentInterval[1] = Math.Max(currentEnd, nextEnd);
            } else {
                currentInterval = interval;
                merged.Add(currentInterval);
            }
        }

        return merged.ToArray();
    }
}

Dart

import 'dart:math';

class Solution {
  List<List<int>> merge(List<List<int>> intervals) {
    if (intervals.isEmpty) { return []; }

    intervals.sort((a, b) => a[0].compareTo(b[0]));

    List<List<int>> merged = [];
    List<int> currentInterval = intervals[0];
    merged.add(currentInterval);

    for (List<int> interval in intervals) {
      int currentEnd = currentInterval[1];
      int nextStart = interval[0];
      int nextEnd = interval[1];

      if (currentEnd >= nextStart) {
        currentInterval[1] = max(currentEnd, nextEnd);
      } else {
        currentInterval = interval;
        merged.add(currentInterval);
      }
    }

    return merged;
  }
}

PHP

class Solution {
    public function merge(array $intervals): array {
        if (empty($intervals)) { return []; }

        usort($intervals, function($a, $b) { return $a[0] - $b[0]; });

        $merged = [$intervals[0]];

        for ($i = 1; $i < count($intervals); $i++) {
            $lastMerged = &$merged[count($merged) - 1];
            $current = $intervals[$i];

            if ($current[0] <= $lastMerged[1]) {
                $lastMerged[1] = max($lastMerged[1], $current[1]);
            } else {
                $merged[] = $current;
            }
        }

        return $merged;
    }
}

Ruby

class Solution
  def merge(intervals)
    return [] if intervals.nil? || intervals.empty?

    intervals.sort_by! { |interval| interval[0] }

    merged = []
    current_interval = intervals[0]
    merged << current_interval

    intervals.each do |interval|
      current_end = current_interval[1]
      next_start = interval[0]
      next_end = interval[1]

      if current_end >= next_start
        current_interval[1] = [current_end, next_end].max
      else
        current_interval = interval
        merged << current_interval
      end
    end

    merged
  end
end