Coding

Merge Intervals

Intervals · Medium

IntervalsMedium

Overview

Merge Intervals: collapse a list of possibly overlapping ranges into the minimal set of disjoint intervals. Sort by start, then sweep, extending the current interval's end whenever the next one overlaps.

How it works

Intervals

ClientServiceEdgeData

Step by step, with examples

1
Intervals
- Combine overlapping ranges.
2
By start
- Order intervals by start.
3
Merge
- Extend the end while ranges overlap.
4
Merged list
- Emit the non-overlapping set.
- Example: [[1,6],[8,10]]

Problem

Given a collection of intervals, merge all overlapping intervals and return the non-overlapping result.

Approach

Sort by start
Walk through, extending the last interval when it overlaps, otherwise starting a new one

Solution

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

Complexity

Time O(n log n), Space O(n).

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions