Intervals

Array Sweeps

Signal

Merge/insert overlapping intervals, meeting rooms

Template

Sort by start, merge when curr.start <= prev.end.

Worked example (1)

#6

Intervals

Sort + Interval Sweep

Given a list of intervals, merge all that overlap.

function merge(intervals: number[][]): number[][] {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const res: number[][] = [];
  for (const [start, end] of sorted) {
    const last = res[res.length - 1];
    if (last && start <= last[1]) last[1] = Math.max(last[1], end); // overlap → extend
    else res.push([start, end]);
  }
  return res;
}

def merge(intervals)
  res = []
  intervals.sort_by(&:first).each do |start, finish|
    last = res.last
    if last && start <= last[1]
      last[1] = [last[1], finish].max # overlap -> extend
    else
      res << [start, finish]
    end
  end
  res
end