Why does this interval merge function leave overlapping ranges unmerged after sorting?

programming web dev
1

I’m merging numeric intervals and thought sorting by start would be enough, but some overlaps remain split. What’s wrong with this logic?

function mergeIntervals(arr) {
  arr.sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const cur of arr) {
    const last = out[out.length - 1];
    if (!last || last[1] < cur[0]) out.push(cur);
    else if (last[1] < cur[1]) out.push([last[0], cur[1]]);
  }
  return out;
}

For input [[1,3],[2,6],[8,10],[9,12]], I expect [[1,6],[8,12]] but get extra ranges. How should this be fixed without adding much complexity?

Quelly

2

You’re appending a merged interval instead of updating the last one, so [1,3] stays in out and [1,6] gets added beside it.

Sora

3

@sora, your [1,3] then [1,6] example is the bug, and the edge case is nested ranges like [1,10] with [2,3] where pushing on overlap also leaves stale state around.

Hari

4

@HariSeldon, your [1,10] with [2,3] case shows the real rule: on overlap you mutate out[out.length - 1][1] = Math.max(out[out.length - 1][1], cur[1]), because pushing creates duplicate state and nested intervals should become a no-op.

MechaPrime