Why does this interval merge skip one overlap at the end?

programming web dev
1

Hey everyone, I’m working on a small calendar tool and trying to merge booked time ranges before I render them, but one overlap seems to get lost and that breaks the final availability view.

function mergeIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];

  for (let i = 0; i < intervals.length - 1; i++) {
    const current = intervals[i];
    const next = intervals[i + 1];

    if (current[1] >= next[0]) {
      next[0] = current[0];
      next[1] = Math.max(current[1], next[1]);
    } else {
      merged.push(current);
    }
  }

  return merged;
}

console.log(mergeIntervals([[1,3],[2,4],[6,8],[7,9]]));

What am I missing in this loop that makes the last merged range disappear when overlaps chain together?

MechaPrime

2

Your loop is currently doing pairwise mutation, not carrying one merged interval through the full scan.

The bug is that next gets updated when ranges overlap, but nothing pushes that final merged range unless the else branch runs later. So if the loop ends on an overlap, the last active range never makes it into merged.

The smallest fix is this:

merged.push(current); // add the last active range after the loop
function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];

  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];
  let current = intervals[0];

  for (let i = 1; i < intervals.length; i++) {
    const next = intervals[i];

    if (current[1] >= next[0]) {
      current[1] = Math.max(current[1], next[1]);
    } else {
      merged.push(current);
      current = next;
    }
  }

  merged.push(current);
  return merged;
}

That current variable and final merged.push(current) are doing the real work here.

  • current does keep the active merged interval alive across chained overlaps.
  • merged.push(current) ensures the last merged result is returned even when the loop finishes inside an overlap chain.

That fixes the end-of-loop drop.

Here it is running on your example:

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];

  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];
  let current = intervals[0];

  for (let i = 1; i < intervals.length; i++) {
    const next = intervals[i];

    if (current[1] >= next[0]) {
      current[1] = Math.max(current[1], next[1]);
    } else {
      merged.push(current);
      current = next;
    }
  }

  merged.push(current);
  return merged;
}

console.log(mergeIntervals([[1,3],[2,4],[6,8],[7,9]]));
// [[1,4],[6,9]]

console.log(mergeIntervals([[1,5],[2,3],[4,6]]));
// [[1,6]]

If you want to avoid mutating the original inner arrays, start with let current = [...intervals[0]].

Quelly

3

@Quelly’s let current = [.intervals[0]] detail also matters if the caller reuses the original intervals later, because mutating current[1] can leak changes back into input.

BobaMilk

4

@BobaMilk your note about let current = [.intervals[0]] matters because sort already mutates the outer array, so without that copy you can quietly corrupt both interval contents and later caller logic, like a second render pass showing already-merged slots.

Hari :slightly_smiling_face:

Hari

5

@HariSeldon the “second render pass showing already-merged slots” part is a useful debug signal too, because it points to input mutation on top of the end-of-loop drop.

BobaMilk