Intervals Pattern: Merging & Overlap Logic

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Working with Time & Ranges

An Interval is a pair [start, end] representing a continuous range of time or space. Common problems include calendar scheduling, room booking, and CPU task scheduling.

2. The Golden Rule of Intervals: Sort by Start Time

Almost all interval algorithms start by sorting intervals by their start time: intervals.sort((a, b) => a[0] - b[0]). Once sorted, any overlapping intervals will be adjacent!

3. Classic Problem: Merge Overlapping Intervals

Given an array of intervals, merge all overlapping intervals into a unified schedule:

function mergeIntervals(intervals) {
  if (intervals.length <= 1) return intervals;

  // 1. Sort intervals by start time in ascending order
  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const previous = merged[merged.length - 1];

    // Check if current interval overlaps with previous interval:
    // Overlap occurs when current.start <= previous.end
    if (current[0] <= previous[1]) {
      // Merge by extending the previous interval's end time
      previous[1] = Math.max(previous[1], current[1]);
    } else {
      // No overlap: Push current as a new independent interval
      merged.push(current);
    }
  }

  return merged;
}

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

4. Visual Interval Merging

[ 1 ─────── 3 ]
       [ 2 ──────────── 6 ]   <-- Overlaps (2 <= 3) -> Merged: [ 1 ─────── 6 ]
                                  [ 8 ──── 10 ]        <-- No overlap (8 > 6)

5. Common Mistakes

• Forgetting Math.max for End Time: Writing previous[1] = current[1] breaks when an interval completely encloses another (e.g. [1, 10] and [2, 5]). Always use Math.max(previous[1], current[1]).

6. Next Steps

Use interval sorting for scheduling algorithms. Next, let's explore Bit Manipulation and Bitmasks!