📅 Intervals

A learning sheet — almost every interval problem starts the same way: sort by one endpoint, then sweep once. Picking which endpoint is the whole game.

🧠 1 · How to think (and invent it)

An interval is [start, end]. The universal first move is to sort — almost always by start (to merge/detect overlaps) or by end (to greedily fit the most). Once sorted, related intervals become adjacent, and one linear sweep does the work.

Memorize the overlap test and you'll never fumble a condition: [a,b] and [c,d] overlap iff a ≤ d and c ≤ b. After sorting by start, it simplifies to "the next one starts before the current one ends": next.start ≤ cur.end.

Watch it get invented — Merge Intervals

1. Start brute. Compare every pair, union overlaps → O(n²) and fiddly.
2. The leap. Sort by start. Now overlapping intervals sit next to each other. Carry a running "current merged" interval; if the next one starts within it, stretch the end; otherwise the current one is closed — push it and open a new one.
3. Why sorting makes it safe. Once an interval doesn't overlap the running merge, no later interval can either (they all start even later) — so the running merge is final the moment a gap appears.
4. Payoff. O(n log n) to sort, then O(n) to sweep.

🎯 2 · Attack plan

🔎 3 · Recognition map

🧩 4 · The four core patterns

Each: a one-liner, a 🔑 invariant, a template, a 🎤 interview lens. Notice §4.1 sorts by start; §4.4 sorts by end — that's the crux.

4.1 · Merge overlapping (sort by start)

“Sort by start; extend the running interval or open a new one at each gap.”

// Merge Intervals
function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);              // by START
  const out: number[][] = [];
  for (const [s, e] of intervals) {
    const last = out[out.length - 1];
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);  // overlap → extend
    else out.push([s, e]);                                    // gap → new interval
  }
  return out;
}

// Insert Interval into a sorted, non-overlapping list — three phases
function insert(intervals: number[][], n: number[]): number[][] {
  const out: number[][] = []; let i = 0, m = intervals.length;
  while (i < m && intervals[i][1] < n[0]) out.push(intervals[i++]);     // entirely before
  while (i < m && intervals[i][0] <= n[1]) {                            // overlapping → absorb
    n = [Math.min(n[0], intervals[i][0]), Math.max(n[1], intervals[i][1])]; i++;
  }
  out.push(n);
  while (i < m) out.push(intervals[i++]);                              // entirely after
  return out;
}

4.2 · Sweep line — +1 / −1 events

“Turn each interval into a +1 at start and a −1 at end; sweep the timeline.”

Setup: concurrency questions ("how many overlap at once?") become a running counter over time-ordered events. The peak counter is the answer.

// Minimum Meeting Rooms — peak concurrency via events
function minMeetingRooms(intervals: number[][]): number {
  const events: [number, number][] = [];
  for (const [s, e] of intervals) { events.push([s, +1]); events.push([e, -1]); }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);   // ties: −1 (end) before +1 (start)
  let cur = 0, best = 0;
  for (const [, delta] of events) { cur += delta; best = Math.max(best, cur); }
  return best;
}

4.3 · Intersection of two sorted lists

“Overlap = [max(starts), min(ends)]; advance whoever ends first.”

Setup: two interval lists, each sorted and internally non-overlapping. A pointer in each; the one that ends earlier can't intersect anything further, so it moves on. This is the two-sequence two-pointer wearing an interval costume.

function intervalIntersection(A: number[][], B: number[][]): number[][] {
  const out: number[][] = []; let i = 0, j = 0;
  while (i < A.length && j < B.length) {
    const lo = Math.max(A[i][0], B[j][0]);
    const hi = Math.min(A[i][1], B[j][1]);
    if (lo <= hi) out.push([lo, hi]);             // non-empty overlap
    if (A[i][1] < B[j][1]) i++; else j++;          // drop the one ending first
  }
  return out;
}

4.4 · Greedy by end — fit the most

“Want the most non-overlapping? Keep the one that ends earliest.”

Setup: to maximize how many intervals you keep (or minimize removals/arrows), sort by end and greedily take each interval that starts after the last kept one ends.

// Non-overlapping Intervals — fewest removals to make the rest disjoint
function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);          // by END
  let end = -Infinity, kept = 0;
  for (const [s, e] of intervals) {
    if (s >= end) { kept++; end = e; }             // compatible → keep it
  }
  return intervals.length - kept;                  // the rest must be removed
}

⏱️ 5 · Complexity

⚠️ 6 · Pitfalls — and the test that catches each

// 1094 Car Pooling — difference array over positions
function carPooling(trips: number[][], capacity: number): boolean {
  const diff: number[] = new Array(1002).fill(0);
  for (const [n, from, to] of trips) { diff[from] += n; diff[to] -= n; }   // they leave AT 'to' (exclusive)
  let load = 0;
  for (const d of diff) { load += d; if (load > capacity) return false; }
  return true;
}

// 3355 Zero Array Transformation I — coverage count per index must be >= nums[i]
function isZeroArray(nums: number[], queries: number[][]): boolean {
  const diff: number[] = new Array(nums.length + 1).fill(0);
  for (const [l, r] of queries) { diff[l]++; diff[r + 1]--; }
  let cur = 0;
  for (let i = 0; i < nums.length; i++) { cur += diff[i]; if (nums[i] > cur) return false; }
  return true;
}

// 731 My Calendar II — allow double booking, reject triple
class MyCalendarTwo {
  private booked: number[][] = [];
  private overlaps: number[][] = [];                       // regions already booked twice
  book(s: number, e: number): boolean {
    for (const [a, b] of this.overlaps) if (s < b && a < e) return false;     // would be a 3rd booking
    for (const [a, b] of this.booked) {
      const lo = Math.max(s, a), hi = Math.min(e, b);
      if (lo < hi) this.overlaps.push([lo, hi]);
    }
    this.booked.push([s, e]);
    return true;
  }
}

// 715 Range Module — sorted disjoint half-open intervals [l, r)
class RangeModule {
  private iv: number[][] = [];
  addRange(l: number, r: number): void {
    const out: number[][] = []; let placed = false;
    for (const [a, b] of this.iv) {
      if (b < l) out.push([a, b]);                                             // strictly before (touching merges)
      else if (a > r) { if (!placed) { out.push([l, r]); placed = true; } out.push([a, b]); }
      else { l = Math.min(l, a); r = Math.max(r, b); }                         // overlaps or touches → absorb
    }
    if (!placed) out.push([l, r]);
    this.iv = out;
  }
  removeRange(l: number, r: number): void {
    const out: number[][] = [];
    for (const [a, b] of this.iv) {
      if (b <= l || a >= r) out.push([a, b]);
      else { if (a < l) out.push([a, l]); if (b > r) out.push([r, b]); }       // one interval can split in two
    }
    this.iv = out;
  }
  queryRange(l: number, r: number): boolean { return this.iv.some(([a, b]) => a <= l && r <= b); }
}

📊 Coverage — pattern → LeetCode (medium & hard)

Own each pattern and these are in range. Bold = Hard tier.

✅ 7 · Self-check

Cover the right column (blurred — hover/tap to reveal). Say your answer out loud first.

Write these cold (no peeking)

• merge merge + insert
• sweep minMeetingRooms (events, end-before-start)
• intersect intervalIntersection
• greedy eraseOverlapIntervals (sort by end)

For each: write "sort by start or end? what's the overlap test?" as a comment before the loop.