Do [1,4] and [4,5] Overlap? Answer That First

Open LeetCode 56, Merge Intervals, and read the second example:

Input: intervals = [[1,4],[4,5]]. Output: [[1,5]]. Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Now open LeetCode 435, Non-overlapping Intervals, which sits in the same tag and gets recommended as the natural follow-up:

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Same site, adjacent problems, opposite rule for the same pair of numbers. That is not LeetCode being careless. It is the single genuine ambiguity in this whole family of problems, and it is where the bugs live. Every interval algorithm you will ever write has a < or a <= at its centre, and nobody can tell you which one is correct without knowing what the numbers mean.

So decide first, then write the loop.

The two conventions

A pair [a, b] is a closed interval when it includes both endpoints. Under closed ends, [1,4] and [4,5] both contain the point 4, so they overlap and they merge. That is LeetCode 56 and 57, and it is right for anything that counts discrete units: IP address ranges, byte ranges in an HTTP Range header, line spans in a git diff. Bytes 1 through 4 and bytes 4 through 5 really do fight over byte 4.

A pair [a, b) is half-open when it includes the start and excludes the end. Under half-open ends, [1,4) and [4,5) share nothing. That is LeetCode 435, and it is right for anything on a continuous timeline: calendars, meeting rooms, shift rosters, booking systems. A meeting that ends at 4pm and one that starts at 4pm do not need two rooms.

The failure mode in production is never "we picked the wrong one". It is that half the codebase assumed one and half assumed the other, because nobody wrote it down. Room booking says two meetings conflict; the calendar UI draws them side by side; the reminder job fires once.

Put the decision in exactly one function

There is a strong temptation to open with the merge loop and hard-code <= into it. Resist it, because the same comparison shows up four more times before you are done, and they drift.

export type Interval = [number, number];
export type Ends = "closed" | "half-open";
 
// The only place in the codebase that knows what "overlap" means.
export function overlaps(aEnd: number, bStart: number, ends: Ends): boolean {
  return ends === "closed" ? bStart <= aEnd : bStart < aEnd;
}
 
// Half-open makes [3,3) the empty set. It merges with nothing and it
// belongs in no output. Closed intervals keep [3,3] — it is the point 3.
export function normalise(intervals: Interval[], ends: Ends): Interval[] {
  const kept = ends === "closed" ? intervals : intervals.filter((iv) => iv[0] < iv[1]);
  return kept.map((iv): Interval => [iv[0], iv[1]]);
}

That normalise also does something less obvious: it copies. More on why in a moment.

Merge, with the convention passed in

export function mergeIntervals(intervals: Interval[], ends: Ends = "closed"): Interval[] {
  const sorted = normalise(intervals, ends);
  if (sorted.length === 0) return [];
 
  sorted.sort((a, b) => a[0] - b[0]);
 
  const out: Interval[] = [sorted[0]];
  for (let i = 1; i < sorted.length; i++) {
    const last = out[out.length - 1];
    const next = sorted[i];
    if (overlaps(last[1], next[0], ends)) {
      last[1] = Math.max(last[1], next[1]);
    } else {
      out.push(next);
    }
  }
  return out;
}

Sorting by start is what makes one pass enough. Once A starts no later than B, the only question left is whether B starts before A finishes, which is the one thing overlaps was written to answer. Watch the Math.max on the end, though: [1,10] swallows [3,4] entirely, and taking next[1] blindly would shrink the run back to 4.

The comparator above breaks ties on equal starts arbitrarily, which looks like a lurking bug. It is not. I checked it exhaustively: every multiset of one to four intervals with coordinates in 0..5, merged three ways — no tie-break, ascending end, descending end. All 12,649 multisets produced identical output. Once Math.max is doing the extension, the order of equal-start intervals cannot change the result, so leave the comparator simple.

Insert, driven by the same predicate

LeetCode 57 hands you an array that is already sorted and already non-overlapping, plus one new interval. Pushing it and re-sorting works but throws away what you were given. The sweep walks the array once, in three phases, and every phase asks overlaps.

export function insertInterval(
  intervals: Interval[],
  newInterval: Interval,
  ends: Ends = "closed",
): Interval[] {
  if (ends === "half-open" && newInterval[0] >= newInterval[1]) {
    return normalise(intervals, ends); // inserting the empty set
  }
  const rest = normalise(intervals, ends);
  const grown: Interval = [newInterval[0], newInterval[1]];
  const out: Interval[] = [];
  let i = 0;
 
  // Phase 1 — everything that ends before the new interval starts.
  while (i < rest.length && !overlaps(rest[i][1], grown[0], ends)) {
    out.push(rest[i]);
    i++;
  }
  // Phase 2 — everything that starts before the new interval ends. Absorb it.
  while (i < rest.length && overlaps(grown[1], rest[i][0], ends)) {
    grown[0] = Math.min(grown[0], rest[i][0]);
    grown[1] = Math.max(grown[1], rest[i][1]);
    i++;
  }
  out.push(grown);
  // Phase 3 — the untouched tail.
  while (i < rest.length) {
    out.push(rest[i]);
    i++;
  }
  return out;
}

Notice that phase 1 is the negation of phase 2 with the arguments swapped. That symmetry is what you get for spending a function on the decision, and it is why switching to "half-open" needs no edit here at all.

Who owns the arrays you hand back

The version of this code you will find in most write-ups sorts the caller's array in place, then reuses the caller's inner arrays in the output. Both of those are real bugs waiting for a second reader.

Sorting in place destroys the caller's ordering. If the array came from a database query ordered by creation time, that ordering is gone, silently, in a function called merge.

The aliasing is worse. If out[0] is the same object as intervals[3], then a later write to either one changes both, arbitrarily far away in the program:

// The version you will find almost everywhere: sorts in place, reuses the
// caller's inner arrays in the output.
function mergeSharedRefs(intervals) {
  if (intervals.length === 0) return [];
  intervals.sort((a, b) => a[0] - b[0]);
  const kept = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const run = kept[kept.length - 1];
    if (intervals[i][0] <= run[1]) run[1] = Math.max(run[1], intervals[i][1]);
    else kept.push(intervals[i]);
  }
  return kept;
}
 
const bookings = [[1, 3], [2, 6], [8, 10]];
const busy = mergeSharedRefs(bookings);
console.log(busy);         // [ [ 1, 6 ], [ 8, 10 ] ]
console.log(bookings);     // [ [ 1, 6 ], [ 2, 6 ], [ 8, 10 ] ]  <- caller's data rewritten
bookings[0][1] = 0;        // caller edits what it still thinks is its own array
console.log(busy);         // [ [ 1, 0 ], [ 8, 10 ] ]  <- a range that ends before it starts

The insert variants have the same problem one level down: they mutate the newInterval argument to grow it, then put that same object in the result. Reuse the variable for a second call and the second answer is computed from the grown interval, not the one you passed. normalise copying every interval, and insertInterval copying newInterval into grown, is what removes both classes of bug.

That copy is not free, and I would rather give you the number than wave it away. On 1,280,000 intervals, insertInterval with the copy took 78.5 ms against 4.9 ms for the identical algorithm that reuses the caller's inner arrays — 16x, and it is all allocation. Inside mergeIntervals you will never see it, because the sort next door costs six times more. Inside insertInterval, where there is no sort, the copy is the bill. So: copy by default, and if profiling puts you in the 4.9 ms case, drop the copy and write the aliasing into the function's name and its doc comment rather than pretending it is not there.

Proving it, rather than tracing it

Hand-tracing a merge loop proves nothing; the bugs live in the cases you did not think to trace. Point-set comparison against a deliberately stupid oracle does better.

// Repeatedly merge any overlapping pair until nothing changes. Quadratic and
// obviously correct. An oracle you have to reason about is not an oracle.
function slowFixpoint(intervals, ends) {
  const hit = (a, b) => ends === "closed"
    ? Math.max(a[0], b[0]) <= Math.min(a[1], b[1])
    : Math.max(a[0], b[0]) < Math.min(a[1], b[1]);
  const xs = normalise(intervals, ends);
  for (let changed = true; changed; ) {
    changed = false;
    search: for (let i = 0; i < xs.length; i++)
      for (let j = i + 1; j < xs.length; j++)
        if (hit(xs[i], xs[j])) {
          const m = [Math.min(xs[i][0], xs[j][0]), Math.max(xs[i][1], xs[j][1])];
          xs.splice(j, 1); xs.splice(i, 1); xs.push(m);
          changed = true;
          break search;
        }
  }
  return xs.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
}
 
const check = (cond, msg) => { if (!cond) throw new Error(msg); };
 
function randomIntervals(n, lo, hi, maxLen) {
  const out = [];
  for (let i = 0; i < n; i++) {
    const a = lo + ((Math.random() * (hi - lo + 1)) | 0);
    out.push([a, a + ((Math.random() * (maxLen + 1)) | 0)]);
  }
  return out;
}
 
for (const ends of ["closed", "half-open"]) {
  for (let t = 0; t < 60000; t++) {
    const input = randomIntervals((Math.random() * 9) | 0, 0, 8, 2); // tight range = many exact touches
    const want = JSON.stringify(slowFixpoint(input, ends));
    check(JSON.stringify(mergeIntervals(input, ends)) === want, `merge ${ends} ${JSON.stringify(input)}`);
  }
}
console.log("ok");

Keep the coordinate range small. Spread the numbers out and you almost never generate a pair that touches at exactly one point, which is the only case the whole article is about. Across four range profiles and both conventions I ran 480,000 cases through this — 240,000 for mergeIntervals, 240,000 for insertInterval — with zero mismatches.

Four fifths of the run time is Array#sort

Quoting complexity is cheaper than measuring it, and it hides things. Measure it.

import { performance } from "node:perf_hooks";
 
const disjointRun = (n) => { const a = []; for (let i = 0; i < n; i++) a.push([i * 3, i * 3 + 1]); return a; };
const shuffleRun = (n) => {
  const a = disjointRun(n);
  for (let i = a.length - 1; i > 0; i--) { const j = (Math.random() * (i + 1)) | 0; [a[i], a[j]] = [a[j], a[i]]; }
  return a;
};
 
function benchOne(fn, makeArgs, reps = 9) {
  for (let i = 0; i < 3; i++) fn(...makeArgs());
  const ms = [];
  for (let r = 0; r < reps; r++) {
    const args = makeArgs();
    const t = performance.now();
    fn(...args);
    ms.push(performance.now() - t);
  }
  return ms.sort((a, b) => a - b)[(reps / 2) | 0];
}
 
const N = 320_000;
const sortOnly = (a) => a.sort((x, y) => x[0] - y[0]);
console.log("sort, shuffled      ", benchOne(sortOnly, () => [shuffleRun(N)]).toFixed(1), "ms");
console.log("sort, already sorted", benchOne(sortOnly, () => [[...disjointRun(N), [5, 9]]]).toFixed(1), "ms");
console.log("merge, shuffled     ", benchOne(mergeIntervals, () => [shuffleRun(N)]).toFixed(1), "ms");
console.log("merge, pre-sorted   ", benchOne(mergeIntervals, () => [disjointRun(N)]).toFixed(1), "ms");
console.log("insert, worst case  ", benchOne(insertInterval, () => [disjointRun(N), [-5, N * 3 + 5]]).toFixed(1), "ms");

Node v22.22.3, 320,000 intervals, median of nine runs, on a machine with other things happening on it:

sort, shuffled       129.3 ms
sort, already sorted   5.0 ms
merge, shuffled      165.4 ms
merge, pre-sorted     18.0 ms
insert, worst case    10.7 ms

The sweep is not the cost. Merging shuffled input costs 165.4 ms and 129.3 ms of that — around four fifths — is Array#sort. Strip the sort out by feeding it pre-sorted data and the same function finishes in 18.0 ms. Across ten repeats the shuffled sort ranged 118–158 ms and the already-sorted one 4.4–5.4 ms; the ratio between them was the stable part, not the absolute figures.

insertInterval at its worst case, where the new interval swallows all 320,000 existing ones, costs 10.7 ms. The sweep inside it is linear: there is no hidden splice or shift in the loop, and stripped of the copy it times out to a clean straight line. The shipped version's wall clock is not linear, and the other figure in this article is the proof — the same call on 1,280,000 intervals takes 78.5 ms, which is 7.3x for 4x the input. That excess is the per-interval copy meeting the allocator. It moves around between runs, so time this at the size you actually run it at instead of extrapolating from one point.

That ratio is the interesting line. Sorting an already-sorted array takes 5.0 ms against 129.3 ms shuffled, a 26x gap, because V8 has used TimSort since V8 v7.0 / Chrome 70 and TimSort finishes an already-sorted array in linear time — it finds one run and merges nothing (V8 blog). So the "just push it on the end and re-sort" shortcut for insert is not the asymptotic disaster the textbook answer implies. It is a constant-factor loss of roughly an order of magnitude, and it is still the wrong call — but say that, rather than quoting a complexity class you have not measured.

That same post settles a detail people hedge on: in V8 the sort's auxiliary array "never exceeds n/2", so Array#sort on a JavaScript array costs linear extra space. There is no quicksort branch to hand-wave about.

The follow-up about O(1) space

Interviewers like to ask whether you can do insert without the output array, and the usual answer is to splice the overlapping run out of the input and drop the merged interval in its place. It is a fine answer as long as you do not call it constant space.

Array.prototype.splice(i, k, x) builds and returns an array of the k elements it removed. You are discarding that value, but it was allocated. Removing a run of k intervals allocates k slots, and in the worst case k is n — I checked, and splice(0, 1_280_000, [0, 1]) really does hand back all 1,280,000 elements. The garbage collector will clean it up. It is still not O(1).

The time story is split, and worth knowing which side you are on. Against the same algorithm building a fresh output array without per-interval copies, both on 1,280,000 intervals, reusing disjointRun and benchOne from the benchmark above:

function insertNoCopy(iv, ni) {
  const out = [], g = [ni[0], ni[1]];
  let i = 0;
  while (i < iv.length && iv[i][1] < g[0]) { out.push(iv[i]); i++; }
  while (i < iv.length && iv[i][0] <= g[1]) {
    g[0] = Math.min(g[0], iv[i][0]); g[1] = Math.max(g[1], iv[i][1]); i++;
  }
  out.push(g);
  while (i < iv.length) { out.push(iv[i]); i++; }
  return out;
}
function insertSplice(iv, ni) {
  const g = [ni[0], ni[1]];
  let i = 0;
  while (i < iv.length && iv[i][1] < g[0]) i++;
  let j = i;
  while (j < iv.length && iv[j][0] <= g[1]) {
    g[0] = Math.min(g[0], iv[j][0]); g[1] = Math.max(g[1], iv[j][1]); j++;
  }
  iv.splice(i, j - i, g);          // the return value nobody reads
  return iv;
}
 
const BIG = 1_280_000;
const swallowAll = [-5, BIG * 3 + 5], pastTheEnd = [BIG * 3 + 100, BIG * 3 + 200];
for (const [label, arg] of [["worst", swallowAll], ["best", pastTheEnd]]) {
  console.log(label,
    "splice", benchOne(insertSplice, () => [disjointRun(BIG), arg]).toFixed(2),
    "fresh", benchOne(insertNoCopy, () => [disjointRun(BIG), arg]).toFixed(2));
}

worst splice 7.51 fresh 3.33
best splice 2.55 fresh 12.42

Worst case, where the new interval swallows everything, splice is the slower of the two, and it was slower at every size I tried from 20,000 up. Best case, where the new interval lands past the end and absorbs nothing, splice wins by appending one element instead of rebuilding a million-entry array. The multiplier on that second line is the least stable number in this article: 4.9x here, and between 3.6x and 8x on the other two machines this has been run on. Take the sign, not the size.

So the splice version is a real optimisation for sparse inserts into a long list and a pessimisation for the case the interviewer is picturing. Either way it hands back a mutated argument. If someone asks for it, write it, and say which case you are optimising for.

Write it above overlaps

None of this is hard. Sort by start, sweep once, take the max of the ends. What breaks is the part nobody writes down. So write it down — not in a commit message, in a comment sitting directly above overlaps, in words a reader can check against the data. Then when the ticket arrives six months from now saying two adjacent shifts are showing as one, the answer is a one-character edit in one function instead of an afternoon of grepping for <=. And when an interviewer hands you [[1,4],[4,5]] without saying which one they mean, that is the question to ask before you write a line.

Here is the version I would leave in the file:

// Ends are EXCLUSIVE. [1,4) and [4,5) are two separate bookings, and a guest
// checking out on day 4 does not block the guest checking in on day 4.