Coding problem · Medium · Intervals

Merge Intervals

Medium Algorithms & data structures Most askedSeen at Meta, Google, Amazon, Bloomberg, Salesforce

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return the non-overlapping intervals that cover the same ranges, sorted by start. Touching intervals ([1,4] and [4,5]) overlap.

Example 1

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

Example 2

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

Hints

Hint 1

Sort by start time. Then each interval either extends the last merged one or starts a new one.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n log n) · Space O(n)

After sorting by start, keep a result list. If the current interval starts at or before the last merged end, extend that end to max(lastEnd, end) (it might be fully contained); otherwise append a new interval.

Reference solution

function merge(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const [s, e] of sorted) {
    const last = out[out.length - 1];
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);
    else out.push([s, e]);
  }
  return out;
}

function merge(intervals: number[][]): number[][] {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const out: number[][] = [];
  for (const [s, e] of sorted) {
    const last = out[out.length - 1];
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);
    else out.push([s, e]);
  }
  return out;
}

def merge(intervals: list[list[int]]) -> list[list[int]]:
    out: list[list[int]] = []
    for s, e in sorted(intervals):
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

<?php

function merge(array $intervals): array
{
    usort($intervals, fn($a, $b) => $a[0] <=> $b[0]);
    $out = [];
    foreach ($intervals as [$s, $e]) {
        $last = count($out) - 1;
        if ($last >= 0 && $s <= $out[$last][1]) {
            $out[$last][1] = max($out[$last][1], $e);
        } else {
            $out[] = [$s, $e];
        }
    }
    return $out;
}

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> out = new ArrayList<>();
        for (int[] cur : intervals) {
            if (!out.isEmpty() && cur[0] <= out.get(out.size() - 1)[1])
                out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], cur[1]);
            else out.add(new int[]{cur[0], cur[1]});
        }
        return out.toArray(new int[0][]);
    }
}

Common mistakes

Using the current interval's end instead of max(...) — [1,4],[2,3] must stay [1,4].

Insert Interval · Medium
Find Free Meeting Slots · Medium