Merge intervals

Medium TimeO(n log n) SpaceO(n)

Given a list of intervals, each one a start and an end, merge every pair that overlaps and return the intervals that remain. They arrive in no particular order, and intervals that merely touch — one ending exactly where the next begins — count as overlapping.

Examples

Example 1

Input
intervals = [[1, 3], [8, 10], [2, 6], [15, 18]]
Output
[[1,6],[8,10],[15,18]]
Sorted by where they start, the four run [1, 3], [2, 6], [8, 10], [15, 18]. Only the first pair touches — 2 falls inside 1–3 — so those merge into [1, 6], while 8 and 15 each begin after the interval before them has ended.

Example 2

Input
intervals = [[1, 4], [4, 5]]
Output
[[1,5]]
Touching counts as overlapping — 4 is the end of one and the start of the next.

The Code

function merge(intervals) {
  const sorted = intervals.slice().sort((a, b) => a[0] - b[0]);
  const merged = [];
  for (let i = 0; i < sorted.length; i++) {
    const last = merged[merged.length - 1];
    if (!last || last[1] < sorted[i][0]) {
      merged.push([sorted[i][0], sorted[i][1]]);
    } else {
      last[1] = Math.max(last[1], sorted[i][1]);
    }
  }
  return merged;
}
merge([[1, 3], [8, 10], [2, 6], [15, 18]]);
Done
Step through merge([[1, 3], [8, 10], [2, 6], [15, 18]]) call by call

Explanation

Sorted by start, each interval meets only the one being built: it either pushes that one’s end out or closes it and begins a new one.

  1. 1

    merged is empty, so there is no interval being built yet and the first one of the sorted list is pushed as it stands.

    1–3
    0
    2–6
    1
    8–10
    2
    15–18
    3

    merged=[]last=none

    merged → [[1, 3]]

  2. 2

    sorted[1] is 2–6. last[1] is 3, which is not less than the 2 it starts at, so they overlap — and last[1] becomes the larger of the two ends, 6. That assignment goes through a reference: last is the interval held in merged, so merged changes with it and there is nothing to put back.

    1–6
    0
    8–10
    1
    15–18
    2

    merged=[[1, 3]]last=1–3

    last[1] = 6 · merged → [[1, 6]]

  3. 3

    sorted[2] is 8–10, and last[1] is 6, which is less than 8. Nothing overlaps, so 1–6 is finished and 8–10 is pushed as a new interval — which makes it the new last.

    1–6
    0
    8–10
    1

    merged=[[1, 6]]last=1–6

    merged → [[1, 6], [8, 10]]

  4. 4

    sorted[3] is 15–18 and last[1] is 10, so it is pushed too. Four intervals have come out as three.

    1–6
    0
    8–10
    1
    15–18
    2

    merged=[[1, 6], [8, 10]]last=8–10

    merged → [[1, 6], [8, 10], [15, 18]]

More like this

All arrays & loops examples (10) →