lthieu's notes

15-Intervals

10 min read

Navigation

← 14-Greedy | → 16-Math-Number-Theory Giai đoạn: FAANG Mastery — Bổ sung | Độ khó: ⭐⭐⭐⭐ MOC: MOC-DSA-Mastery · Pattern hub: Pattern-Sort-Then-Search

Buổi 15 — Intervals & Sweep Line

1. Analogy & Context

Intervals: Lịch trình cuộc họp

Mỗi cuộc họp = 1 đoạn [start, end). Phòng họp = 1 đường thẳng thời gian. Bài toán intervals = bài toán sắp xếp cuộc họp trên timeline:

  • “Có thể fit tất cả vào 1 phòng?” → Merge / overlap detection.
  • “Cần bao nhiêu phòng tối thiểu?” → Sweep line đếm overlap đỉnh điểm.
  • “Free time chung của tất cả nhân viên?” → Merge unions, bù phần trống.
  • “Insert cuộc họp mới có conflict không?” → Binary search vị trí.

Sweep Line: Thanh quét trên timeline

Tưởng tượng 1 thanh dọc quét từ trái sang phải qua tất cả start và end events. Tại mỗi event, update một counter (active intervals) hoặc heap (current state). Đỉnh điểm của counter chính là max-overlap.

Trend FAANG 2026

Intervals nằm trong top patterns được hỏi nhiều nhất tại Amazon (scheduling) và Google (Calendar / Meeting Rooms / Time-based system design tie-in). 1 round Meta thường có ít nhất 1 bài interval-flavored.

2. The FAANG Standard

Tại sao FAANG yêu thích intervals?

  1. Tự nhiên: lịch họp, gantt chart, booking — đầy bài toán thực tế.
  2. Test multiple skills: sort + greedy + sweep + heap + binary search có thể đan xen.
  3. Edge cases nhiều: touching endpoints, degenerate intervals ([a,a]), reversed.

L4 vs L5 expectation

  • L4: Merge, Insert, Meeting Rooms cơ bản với sort + linear scan.
  • L5+: Sweep line + heap, Employee Free Time, range tree-style solutions, optimize cho streaming inputs (online algo).

3. Decision Tree

Bài cho list intervals → cần xử lý overlap?
├─ "Merge / Union all" → Sort by start, sweep, merge khi overlap
├─ "Insert 1 interval" → Binary search hoặc 3-phase scan
├─ "Đếm số phòng / vehicles cần" → Sweep line (start +1 / end -1) hoặc heap
├─ "Tìm interval không overlap với new" → Sort + binary search
├─ "Free time / Common gap" → Merge → invert
├─ "Skyline" → Sweep line + heap (active heights)
└─ "Range stabbing / point covered by how many" → Sort events + counter

4. TypeScript Templates

4.1 Merge Intervals

// LC #56 — Merge Intervals
// O(N log N) sort + O(N) merge
function merge(intervals: number[][]): number[][] {
  if (intervals.length === 0) return [];
  intervals.sort((a, b) => a[0] - b[0]);
 
  const result: number[][] = [intervals[0].slice()];
  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const [s, e] = intervals[i];
    if (s <= last[1]) {              // overlap (touch endpoint = overlap ở đây)
      last[1] = Math.max(last[1], e);
    } else {
      result.push([s, e]);
    }
  }
  return result;
}

4.2 Insert Interval

// LC #57 — Insert Interval (input đã sorted, không overlap)
// 3 phases: trước newInterval, overlap với newInterval (merge), sau newInterval.
function insert(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];
  let i = 0;
  const n = intervals.length;
 
  // Phase 1: intervals kết thúc TRƯỚC newInterval bắt đầu
  while (i < n && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i++]);
  }
 
  // Phase 2: merge tất cả intervals overlap với 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);
 
  // Phase 3: intervals còn lại sau newInterval
  while (i < n) result.push(intervals[i++]);
 
  return result;
}

4.3 Meeting Rooms I — Có conflict không?

// LC #252 — Can attend all meetings?
function canAttendMeetings(intervals: number[][]): boolean {
  intervals.sort((a, b) => a[0] - b[0]);
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < intervals[i - 1][1]) return false;
  }
  return true;
}

4.4 Meeting Rooms II — Min phòng

// LC #253 — Min meeting rooms (heap-based)
// Greedy: luôn dùng phòng có "end time sớm nhất" hiện tại;
// nếu meeting tiếp theo bắt đầu trước end đó → cần phòng mới.
function minMeetingRooms(intervals: number[][]): number {
  if (intervals.length === 0) return 0;
  intervals.sort((a, b) => a[0] - b[0]);
 
  // Min-heap of end times
  const heap: number[] = [];
  const push = (x: number) => {
    heap.push(x);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] <= heap[i]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const pop = () => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      const n = heap.length;
      while (true) {
        const l = 2*i+1, r = 2*i+2;
        let s = i;
        if (l < n && heap[l] < heap[s]) s = l;
        if (r < n && heap[r] < heap[s]) s = r;
        if (s === i) break;
        [heap[s], heap[i]] = [heap[i], heap[s]];
        i = s;
      }
    }
    return top;
  };
 
  for (const [start, end] of intervals) {
    if (heap.length > 0 && heap[0] <= start) pop(); // tái sử dụng phòng
    push(end);
  }
  return heap.length;
}

4.5 Meeting Rooms II — Sweep Line variant

// O(N log N), elegant alternative. Dùng 2 sorted arrays of starts/ends.
function minMeetingRoomsSweep(intervals: number[][]): number {
  const n = intervals.length;
  const starts = intervals.map(x => x[0]).sort((a, b) => a - b);
  const ends   = intervals.map(x => x[1]).sort((a, b) => a - b);
 
  let rooms = 0, peak = 0, j = 0;
  for (let i = 0; i < n; i++) {
    if (starts[i] < ends[j]) rooms++;     // need new room
    else                     j++;          // reuse: end pointer advances
    peak = Math.max(peak, rooms);
  }
  return peak;
}

4.6 Non-overlapping Intervals (max keep)

// LC #435 — Đã có trong [[14-Greedy]] §4.1, đặt lại đây để tham chiếu nhanh.
function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);
  let kept = 1, lastEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= lastEnd) {
      kept++;
      lastEnd = intervals[i][1];
    }
  }
  return intervals.length - kept;
}

4.7 Employee Free Time

// LC #759 — Mỗi employee có list intervals (sorted, non-overlap).
// Tìm common free time của TẤT CẢ. Gather all → sort → merge → invert.
function employeeFreeTime(schedule: number[][][]): number[][] {
  const all: number[][] = [];
  for (const s of schedule) for (const x of s) all.push(x);
  all.sort((a, b) => a[0] - b[0]);
 
  const merged: number[][] = [all[0].slice()];
  for (let i = 1; i < all.length; i++) {
    const last = merged[merged.length - 1];
    if (all[i][0] <= last[1]) last[1] = Math.max(last[1], all[i][1]);
    else merged.push(all[i].slice());
  }
 
  const free: number[][] = [];
  for (let i = 1; i < merged.length; i++) {
    free.push([merged[i - 1][1], merged[i][0]]);
  }
  return free;
}

4.8 Car Pooling

// LC #1094 — Trip đến đón ở "from" và xuống ở "to".
// Sweep line: tại "from" +numPassengers, tại "to" -numPassengers.
// Nếu lúc nào load > capacity → false.
function carPooling(trips: number[][], capacity: number): boolean {
  // Difference array — locations đến 1000.
  const diff = new Array(1001).fill(0);
  for (const [num, from, to] of trips) {
    diff[from] += num;
    diff[to]   -= num;
  }
  let load = 0;
  for (const d of diff) {
    load += d;
    if (load > capacity) return false;
  }
  return true;
}

4.9 The Skyline Problem (Hard, but classic)

// LC #218 — Skyline using sweep line + max-heap (lazy deletion).
// Events: (x, height, type=start|end). Sort. Tại mỗi x, maintain active max heights.
function getSkyline(buildings: number[][]): number[][] {
  // Events: [x, h, isStart] — start with height h, end at "h" để pop sau.
  const events: [number, number, number][] = [];
  for (const [l, r, h] of buildings) {
    events.push([l, -h, 0]); // start: dùng -h để sort start trước end ở cùng x
    events.push([r, h, 1]);  // end
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
 
  // Max-heap (use negative trick) hoặc multiset. Đơn giản: dùng SortedList substitute.
  // Lazy heap: track active heights, ignore stale.
  const active = new Map<number, number>(); // height -> count
  active.set(0, 1); // ground
 
  const result: number[][] = [];
  let prevMax = 0;
  let i = 0;
  while (i < events.length) {
    const x = events[i][0];
    while (i < events.length && events[i][0] === x) {
      const [, h, t] = events[i];
      const realH = h < 0 ? -h : h;
      if (t === 0) active.set(realH, (active.get(realH) ?? 0) + 1);
      else {
        const c = active.get(realH)! - 1;
        if (c === 0) active.delete(realH);
        else active.set(realH, c);
      }
      i++;
    }
    const currMax = Math.max(...active.keys());
    if (currMax !== prevMax) {
      result.push([x, currMax]);
      prevMax = currMax;
    }
  }
  return result;
}
// Note: above uses Math.max(...keys) for clarity — O(N) per event = O(N²) tổng.
// Production: dùng max-heap với lazy deletion hoặc balanced BST → O(N log N).

5. Complexity Deep-dive

ProblemAlgorithmTimeSpace
Merge IntervalsSort + sweep
Insert Interval3-phase scan
Meeting Rooms ISort + linear
Meeting Rooms II (heap)Sort + heap
Meeting Rooms II (sweep)2-pointer
Non-overlapSort by end
Employee Free TimeMerge all + invert
Car PoolingDifference array
SkylineSweep + heap

6. Edge Cases & Pitfalls

Pitfall 1: Touching endpoints — overlap hay không?

  • Merge Intervals (LC #56): [1,3] và [3,5] thường được coi là overlap → merge thành [1,5]. Dùng <=.
  • Meeting Rooms I (LC #252): kết thúc lúc 9:00, bắt đầu lúc 9:00 → KHÔNG conflict (không overlap). Dùng < strict. Đọc đề kỹ. Hỏi clarification trong interview: “Are touching endpoints considered overlapping?”

Pitfall 2: Sort key sai

  • Merge / Insert: sort theo start.
  • Non-overlap / Min Arrows: sort theo end.
  • Heap-based Meeting Rooms: sort theo start, heap theo end.

Pitfall 3: Interval mutation

Khi push intervals[i] vào result rồi modify in-place sau, kết quả bị “lây”. Luôn intervals[i].slice() hoặc [...intervals[i]].

Pitfall 4: Empty input

Sort của array rỗng không lỗi nhưng truy cập result[0] thì lỗi. Always check if (intervals.length === 0) return ....

Pitfall 5: Sweep line — sort start/end cùng key

Khi start_i == end_j, thứ tự matter:

  • “Touching = overlap” → sort end TRƯỚC start (giảm count trước khi tăng).
  • “Touching ≠ overlap” → sort start TRƯỚC end. Trong skyline: dùng -h cho start để start cao hơn được xử lý trước.

7. Pattern Recognition

Mô tảPattern
”Combine all intervals”Sort by start + merge
”Find conflicts”Sort + adjacent check
”Min number of resources”Sweep line (counter) hoặc heap
”Max k non-overlapping”Sort by end + greedy
”Insert into sorted list”3-phase scan / binary search
”Common free / common busy”Merge → invert
”Range update fast”Difference array (xem Pattern-Prefix-Sum)
“Highest count over time”Sweep + counter
”Skyline / Building outline”Sweep + max-heap (lazy)

8. Top 10 Problems (priority FAANG)

#LCBàiMức
1LC-56Merge IntervalsMedium
2LC-57Insert IntervalMedium
3LC-252Meeting RoomsEasy
4LC-253Meeting Rooms IIMedium
5LC-435Non-overlapping IntervalsMedium
6LC-452Min ArrowsMedium
7LC-759Employee Free TimeHard
8LC-1094Car PoolingMedium
9LC-218SkylineHard
10LC-986Interval List IntersectionsMedium

9. Self-Assessment Checklist

  • Tôi phân biệt được “sort by start” vs “sort by end” cho từng dạng bài.
  • Tôi giải được Insert Interval bằng 3-phase scan trong 12 phút.
  • Tôi cài được Meeting Rooms II bằng cả heap và sweep.
  • Tôi giải Employee Free Time bằng “merge all → invert” mà không nhìn template.
  • Tôi xử lý đúng case “touching endpoints” theo yêu cầu của đề.
  • Tôi nhận ra car pooling = difference array trong < 1 phút.
  • Tôi vẽ được sweep diagram trên giấy cho 5 intervals bất kỳ.

Khi vào interview

Câu đầu tiên cho mọi bài interval: “Are intervals sorted? Are touching endpoints considered overlap?” — 30 giây này tiết kiệm 10 phút debug.

Graph View

Backlinks