Interval Problems — The Complete Guide

Two intervals [a, b] and [c, d] (where a ≤ b and c ≤ d):

OVERLAP if:  a <= d AND c <= b
             (one starts before the other ends, AND vice versa)

NO OVERLAP if:  b < c OR d < a
                (one ends before the other starts)

After sorting by start time (a ≤ c guaranteed):
  OVERLAP if:  c <= b   (next starts before current ends)
  NO OVERLAP:  c > b    (next starts after current ends)

This simplification after sorting is why we ALWAYS sort first.

function mergeIntervals(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]); // sort by start

  const merged: number[][] = [intervals[0]];

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

    if (curr[0] <= last[1]) {
      // Overlap → extend end
      last[1] = Math.max(last[1], curr[1]);
    } else {
      // No overlap → new interval
      merged.push(curr);
    }
  }

  return merged;
}
// Variations:
// - Insert interval: add new interval to list, then merge
// - Find gaps: when curr[0] > last[1], the gap is [last[1], curr[0]]
// - Intersection: instead of extending, take the overlap portion

function maxOverlaps(intervals: number[][]): number {
  // Create events: [time, type] where +1 = start, -1 = end
  const events: [number, number][] = [];

  for (const [start, end] of intervals) {
    events.push([start, 1]);   // interval starts
    events.push([end, -1]);    // interval ends
  }

  // Sort by time. If same time, process ends (-1) before starts (+1)
  // (an interval ending at time T doesn't overlap with one starting at T)
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

  let active = 0;
  let maxActive = 0;

  for (const [, type] of events) {
    active += type;
    maxActive = Math.max(maxActive, active);
  }

  return maxActive;
}
// Variations:
// - Meeting rooms II: maxActive = minimum rooms needed
// - Find the time with max overlaps: track the time when maxActive updates
// - Free time: periods where active === 0

function maxNonOverlapping(intervals: number[][]): number {
  // Sort by END time (critical for greedy correctness)
  intervals.sort((a, b) => a[1] - b[1]);

  let count = 0;
  let lastEnd = -Infinity;

  for (const [start, end] of intervals) {
    if (start >= lastEnd) {
      // No conflict → select this interval
      count++;
      lastEnd = end;
    }
    // else: skip (overlaps with last selected)
  }

  return count;
}
// Why sort by end? The interval that ends earliest leaves the most
// room for future intervals. This greedy choice is provably optimal.
//
// Variations:
// - Min removals to make non-overlapping: n - maxNonOverlapping
// - Min arrows to burst balloons: same logic (arrow at lastEnd pops all overlapping)
// - Erase overlap intervals: count overlapping ones to remove

function insert(
  intervals: number[][],
  newInterval: number[]
): number[][] {
  const result: number[][] = [];
  let i = 0;
  const n = intervals.length;

  // Phase 1: Add all intervals that end BEFORE newInterval starts
  while (i < n && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }

  // Phase 2: Merge all overlapping intervals with newInterval
  while (i < n && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
  }
  result.push(newInterval); // push the merged interval

  // Phase 3: Add all intervals that start AFTER newInterval ends
  while (i < n) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}
// Phase 1: intervals[i][1] < newInterval[0] → entirely before
// Phase 2: intervals[i][0] <= newInterval[1] → overlaps → merge
// Phase 3: everything remaining → entirely after

function intervalIntersection(
  firstList: number[][],
  secondList: number[][]
): number[][] {
  const result: number[][] = [];
  let i = 0, j = 0;

  while (i < firstList.length && j < secondList.length) {
    const lo = Math.max(firstList[i][0], secondList[j][0]);
    const hi = Math.min(firstList[i][1], secondList[j][1]);

    if (lo <= hi) {
      result.push([lo, hi]); // valid intersection
    }

    // Advance the pointer whose interval ends first
    if (firstList[i][1] < secondList[j][1]) {
      i++;
    } else {
      j++;
    }
  }

  return result;
}
// Why advance the earlier-ending interval? It can't intersect with
// anything else in the other list (the other list is sorted, so
// future intervals start even later).

Input: [[1,3], [8,10], [2,6], [15,18]]

Step 1: Sort by start → [[1,3], [2,6], [8,10], [15,18]]

Step 2: Initialize result = [[1,3]]

i=1: curr=[2,6], last=[1,3]
     2 ≤ 3? YES → overlap! Extend: last = [1, max(3,6)] = [1,6]
     result = [[1,6]]

i=2: curr=[8,10], last=[1,6]
     8 ≤ 6? NO → no overlap. Push [8,10]
     result = [[1,6], [8,10]]

i=3: curr=[15,18], last=[8,10]
     15 ≤ 10? NO → no overlap. Push [15,18]
     result = [[1,6], [8,10], [15,18]]

Output: [[1,6], [8,10], [15,18]]

Timeline visualization:
  [1---3]
     [2------6]
                  [8--10]
                              [15--18]
  ─────────────────────────────────────
  [1--------6]   [8--10]     [15--18]  ← merged

Meetings: [[0,30], [5,10], [15,20]]

Step 1: Create events
  [0, +1]  — meeting 1 starts
  [30, -1] — meeting 1 ends
  [5, +1]  — meeting 2 starts
  [10, -1] — meeting 2 ends
  [15, +1] — meeting 3 starts
  [20, -1] — meeting 3 ends

Step 2: Sort by time (ends before starts if same time)
  [0, +1], [5, +1], [10, -1], [15, +1], [20, -1], [30, -1]

Step 3: Sweep
  t=0:  active = 0+1 = 1  maxActive = 1
  t=5:  active = 1+1 = 2  maxActive = 2 ★
  t=10: active = 2-1 = 1
  t=15: active = 1+1 = 2  maxActive = 2
  t=20: active = 2-1 = 1
  t=30: active = 1-1 = 0

Answer: 2 rooms needed (at times 5-10 and 15-20, two meetings overlap)

Timeline:
  Room 1: [0=========================30]
  Room 2:      [5===10]  [15===20]
  ──────────────────────────────────────
  Active:  1    2    1    2    1    0

Input: [[1,2], [2,3], [3,4], [1,3]]
Goal: Remove minimum intervals to make all non-overlapping.

Step 1: Sort by END time → [[1,2], [2,3], [1,3], [3,4]]

Step 2: Greedy select (pick earliest-ending non-conflicting)
  lastEnd = -∞

  [1,2]: 1 ≥ -∞? YES → select. count=1, lastEnd=2
  [2,3]: 2 ≥ 2?  YES → select. count=2, lastEnd=3
  [1,3]: 1 ≥ 3?  NO  → skip (overlaps with last selected)
  [3,4]: 3 ≥ 3?  YES → select. count=3, lastEnd=4

Max non-overlapping = 3
Min removals = 4 - 3 = 1 (remove [1,3])

Why sort by end? [1,3] ends later than [2,3], so keeping [2,3]
leaves more room for [3,4]. Earliest end = most room for future.

Timeline:
  [1-2] [2-3] [3-4]  ← selected (no overlaps)
  [1----3]            ← removed (overlaps with [2,3])
  ──────────────────

What does the problem ask?
├── Merge overlapping intervals into non-overlapping?
│   → Sort by START. Sweep: extend or push. (Template 1)
├── Insert a new interval into a sorted list?
│   → Three phases: before, overlap (merge), after. (Template 1 variant)
├── Find intersection of two interval lists?
│   → Two pointers. Overlap = [max starts, min ends]. Advance earlier end.
├── Check if any intervals overlap (conflict)?
│   → Sort by start. Check if any consecutive pair overlaps.
├── Count max simultaneous overlaps / min resources?
│   → Sweep line: +1 at start, -1 at end. Sort events. Max running count.
│   → Or: min-heap of end times (Meeting Rooms II).
├── Maximize non-overlapping intervals?
│   → Sort by END. Greedy: pick earliest-ending non-conflicting. (Template 3)
├── Minimize removals to eliminate overlaps?
│   → Same as above: removals = n - maxNonOverlapping.
├── Minimum arrows / points to cover all intervals?
│   → Sort by END. Greedy: place arrow at earliest end. (Template 3 variant)
└── Find gaps / free time between intervals?
    → Merge all intervals (Template 1), then gaps = spaces between merged.