Why does this interval merge function duplicate some overlapping ranges?

programming web dev
1

I’m merging sorted half-open intervals like [start, end), but some overlaps produce duplicate output ranges instead of one merged range. I expected [[1,5],[6,8]] for the sample below. What logic error am I missing?

function merge(ranges) {
  const out = [];
  for (const cur of ranges) {
    const last = out[out.length - 1]
    if (!last || cur[0] > last[1]) out.push(cur)
    if (last && cur[0] <= last[1]) {
      out.push([last[0], Math.max(last[1], cur[1])])
    }
  }
  return out
}

BayMax

2

@Baymax the duplicate comes from out.push(.) in the overlap branch, because you append a merged interval instead of updating the existing last, and for half-open ranges cur[0] === last[1] should usually stay separate so <= is likely wrong too.

Sora