DSAMonth 4 · Week 13

Day 62: Interval-based Algorithms (Merge Intervals, Overlaps)

Master the sort-then-sweep pattern that solves the entire family of interval-overlap, merging, and scheduling problems.

Mark this day complete

Study

Concepts

Sort by start time, then sweep once

Nearly every interval problem (merge overlapping intervals, insert an interval, count meeting rooms needed, find free time) becomes tractable once intervals are SORTED BY START TIME — after sorting, you only ever need to compare each interval to the LAST processed one (for merging) or maintain a small structure of currently-active end times (for room-counting), never re-scan the whole list.

The overlap check itself is one line: two intervals `[a, b]` and `[c, d]` (with a ≤ c after sorting) overlap if and only if `c <= b` — internalizing this single comparison is what makes the rest of the pattern fast to derive under pressure.

See It

Visualizations

Visualization

Merging [[1,3],[2,6],[8,10],[15,18]]

[1,3]

first interval

becomes the current merged range

[2,6]

2 <= 3 → overlaps

merge into [1,6]

[8,10]

8 > 6 → no overlap

push [1,6], start new range [8,10]

[15,18]

15 > 10 → no overlap

push [8,10], start new range [15,18]

Build It

Code Examples

Merge overlapping intervals

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);

  const merged = [sorted[0]];
  for (let i = 1; i < sorted.length; i++) {
    const last = merged[merged.length - 1];
    const [start, end] = sorted[i];

    if (start <= last[1]) {          // overlaps the last merged range
      last[1] = Math.max(last[1], end); // extend it
    } else {
      merged.push([start, end]);      // no overlap — start a new range
    }
  }
  return merged;
}

console.log(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]));
// [[1, 6], [8, 10], [15, 18]]

Minimum meeting rooms required — a min-heap of end times

function minMeetingRooms(intervals) {
  if (intervals.length === 0) return 0;
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);

  // A simple array used as a min-heap substitute for clarity;
  // a real min-heap gives O(log n) push/pop instead of O(n log n) re-sort.
  const activeEndTimes = [];

  for (const [start, end] of sorted) {
    activeEndTimes.sort((a, b) => a - b);
    if (activeEndTimes.length && activeEndTimes[0] <= start) {
      activeEndTimes.shift(); // that room just freed up — reuse it
    }
    activeEndTimes.push(end);
  }
  return activeEndTimes.length; // rooms still in use = rooms needed at peak
}

console.log(minMeetingRooms([[0, 30], [5, 10], [15, 20]])); // 2

Remember

Key Takeaways

Sort by start time first — this single step is what makes almost every interval problem solvable in one linear sweep.
Two sorted intervals [a,b] and [c,d] (a <= c) overlap iff c <= b — memorize this one comparison.
Merging: extend the last merged range if the next interval overlaps it, otherwise start a new range.
Room-counting: track active end times; the count of currently-active meetings at any point is the room requirement at that point.
A real min-heap (not a re-sorted array) gives O(n log n) total for the room-counting problem — mention this complexity nuance explicitly in interviews.

Do It

Practice

1Solve "Insert Interval" (insert a new interval into an already-sorted, non-overlapping list and merge as needed) without re-sorting the whole array.
2Solve "Non-overlapping Intervals" (minimum removals to make the rest non-overlapping) — sort by END time instead of start for this one, and explain why.
3Reimplement minMeetingRooms with a real min-heap (or a priority queue library) and compare its complexity to the array-based version.