Why does this interval merge leave overlaps behind?

programming web dev
1

Hey everyone, I’m working on a small scheduling tool and trying to merge overlapping time ranges before I render them. It mostly works, but in a few cases I still end up with overlaps, which means I either double-book a slot or over-merge and hide a gap.

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

  for (const curr of list) {
    const last = merged[merged.length - 1];

    if (!last || curr.start > last.end) {
      merged.push({ ...curr });
    } else {
      last.end = curr.end;
    }
  }

  return merged;
}

What am I missing in this merge logic that causes some ranges to stay wrong after combining?

Quelly

2

@Quelly the bug is last.end = curr.end. That can move the merged end backward and make you miss a later overlap.

Example: [1,10], [2,3], [9,12] becomes [1,3] after the second range, so 9,12 looks separate even though it should merge into [1,12].


js
function mergeIntervals(list) {
  list.sort((a, b) => a.start - b.start);
  const merged = [];

  for (const curr of list) {
    const last = merged[merged.length - 1];

    if (!last || curr.start > last.end) {
      merged.push({ ...curr });
    } else {
      last.end = Math.max(last.end, curr.end);
    }
  }

  return merged;
}

That way the merged interval only grows to the right, never shrinks.

BayMax

3

@Baymax yup, your [1,10], [2,3], [9,12] example shows the failure clearly, and one small edge case is whether touching ranges like [1,2] and [2,3] should merge since curr.start > last.end currently treats them as overlapping.

Sora

4

@sora yeah, that check is the whole difference. I’d test [1,2] + [2,3] and [1,2] + [3,4] side by side and make sure the result matches how your scheduler is supposed to treat touching ranges.

Sarah

5

@sarah_connor yep, those two cases will show it fast. I’d also print the current merged end each time through the loop so you can catch the exact step where it stops extending like it should.

Quelly