Navigation

← 13-Practice-FAANG-2 | → 15-Intervals Giai đoạn: FAANG Mastery — Bổ sung | Độ khó: ⭐⭐⭐⭐ MOC: MOC-DSA-Mastery

Buổi 14 — Greedy Algorithms

1. Analogy & Context

Greedy: Người leo núi cận thị

Tưởng tượng bạn leo núi mà chỉ thấy được trong vòng 2 mét. Bạn áp dụng nguyên tắc “luôn bước về phía dốc lên cao nhất ngay trước mặt” — không biết toàn cảnh, chỉ tin rằng “tối ưu local sẽ dẫn tới tối ưu global”.

Khi đúng: bạn về đích nhanh, không cần lưu lịch sử các nhánh đã thử.
Khi sai: bạn kẹt ở local maximum (đỉnh đồi nhỏ) trong khi đỉnh thật ở phía xa.

Khác biệt với DP

	Greedy	DP
Quyết định	”Best lúc này” — không nhìn lại	Khám phá nhiều lựa chọn, lưu tối ưu
Bắt buộc	Greedy choice property + optimal substructure	Chỉ cần optimal substructure
Time	Thường $O (N lo g N)$ (do sort) hoặc $O (N)$	Thường $O (N \cdot K)$
Khi sai	Sai hoàn toàn — local trap	Vẫn đúng (chậm hơn)

Khi nào greedy ĐÚNG?

Bạn phải chứng minh được “local choice ⇒ optimal”. Hai kỹ thuật chứng minh chính:

Exchange argument: nếu có optimal solution khác lựa chọn của greedy, ta swap dần để biến optimal thành greedy mà không làm xấu kết quả.

Greedy stays ahead: sau bước $k$ greedy luôn ở vị trí tốt hơn hoặc bằng bất kỳ thuật toán nào khác.

2. The FAANG Standard

Greedy đứng trong top-10 patterns được hỏi nhất tại Meta/Google/Amazon (2025-2026). FAANG đặc biệt yêu thích greedy vì nó test 2 năng lực:

Pattern recognition: nhận ra “đây là greedy được, không cần DP”.
Proof articulation: giải thích vì sao greedy đúng (exchange argument). Đây là điều AI không tự sinh được — interviewer dùng để filter.

L4 vs L5 expectation

L4: Implement đúng + biết khi greedy sai → fallback DP.
L5+: Trình bày exchange argument trên giấy. Phân biệt khi nào dùng heap-based greedy vs sort-based greedy. Suy luận về stability của ordering.

3. Decision Tree — Khi nào Greedy?

Bài hỏi "tối ưu" (max/min/min count)?
├─ Có overlapping subproblem? → DP
├─ Có greedy choice property?
│   ├─ Sort-based: sắp xếp theo deadline / weight / end / ratio → quét tuần tự
│   ├─ Heap-based: lúc nào cũng cần "hiện tại lớn nhất / nhỏ nhất" → priority queue
│   └─ Two-pointer greedy: thu hẹp từ 2 đầu (Container Most Water)
└─ Không chắc → thử greedy với 2-3 ví dụ phản biện. Nếu không break → có thể đúng.

Heuristic chọn key sort

“Hoàn thành nhiều nhất” → sort theo end time (interval scheduling).

“Tổng giá trị max với weight ≤ W” và items chia được → sort theo value/weight ratio (fractional knapsack).

“Số xe / số phòng / số arrows tối thiểu” → thường sort theo start rồi sweep.

“Đoàn người được sắp xếp lại” → sort theo cặp [h, k] đặc biệt (LC #406).

4. TypeScript Templates

4.1 Activity Selection / Interval Scheduling Maximization

// LC #435 — Non-overlapping Intervals (count to remove)
// Greedy: sort theo END, luôn chọn interval kết thúc sớm nhất chưa overlap.
// Exchange argument: nếu optimal chọn interval kết thúc muộn hơn greedy,
// ta swap nó về greedy → optimal vẫn ≥ greedy.
function eraseOverlapIntervals(intervals: number[][]): number {
  if (intervals.length === 0) return 0;
  intervals.sort((a, b) => a[1] - b[1]); // sort theo end ASC
 
  let kept = 1;
  let lastEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= lastEnd) {  // không overlap
      kept++;
      lastEnd = intervals[i][1];
    }
    // else: bỏ interval này
  }
  return intervals.length - kept;
}

4.2 Jump Game I — Reach the End

// LC #55 — Jump Game I
// Greedy: track farthest reachable. Nếu i > farthest → kẹt.
function canJump(nums: number[]): boolean {
  let farthest = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false;
    farthest = Math.max(farthest, i + nums[i]);
  }
  return true;
}

4.3 Jump Game II — Min Jumps

// LC #45 — Jump Game II — BFS-flavored greedy
// Mỗi "jump" mở rộng frontier; đếm số lần đổi frontier để tới end.
function jump(nums: number[]): number {
  let jumps = 0, currEnd = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {  // < n-1: không jump khi đã ở cuối
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currEnd) {                       // hết frontier hiện tại
      jumps++;
      currEnd = farthest;
    }
  }
  return jumps;
}

4.4 Gas Station — Circular Tour

// LC #134 — Gas Station
// Greedy: nếu total(gas) >= total(cost), tồn tại starting point.
// Track tank: nếu negative tại i → start phải > i (tất cả j ≤ i fail).
function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    total += diff;
    tank += diff;
    if (tank < 0) {           // bất kỳ start ≤ i đều fail
      start = i + 1;
      tank = 0;
    }
  }
  return total >= 0 ? start : -1;
}

4.5 Task Scheduler

// LC #621 — Task Scheduler
// Heap-based greedy: luôn execute task có freq lớn nhất chưa cooldown.
// Hoặc công thức: max(N, (maxFreq-1)*(n+1) + countOfMaxFreqTasks).
function leastInterval(tasks: string[], n: number): number {
  const freq: Record<string, number> = {};
  for (const t of tasks) freq[t] = (freq[t] ?? 0) + 1;
  const counts = Object.values(freq);
 
  const maxFreq = Math.max(...counts);
  const numMax = counts.filter(c => c === maxFreq).length;
 
  // Frame: (maxFreq-1) blocks of size (n+1) + tail có numMax tasks
  return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + numMax);
}

Tại sao công thức này đúng?

Tasks có freq cao nhất tạo “cột sống” A _ _ A _ _ A. Mỗi gap có size n. Filler nếu đủ → fill kín, ans = tasks.length. Filler không đủ → cần idle slot, ans = công thức frame.

4.6 Reorganize String

// LC #767 — Reorganize String — Heap greedy
// Mỗi bước: chọn 2 char có freq cao nhất (chưa kề char trước) để place.
function reorganizeString(s: string): string {
  const freq: Record<string, number> = {};
  for (const c of s) freq[c] = (freq[c] ?? 0) + 1;
 
  // Max-heap of [count, char]
  const heap: [number, string][] = [];
  const push = (item: [number, string]) => {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p][0] >= heap[i][0]) 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 big = i;
        if (l < n && heap[l][0] > heap[big][0]) big = l;
        if (r < n && heap[r][0] > heap[big][0]) big = r;
        if (big === i) break;
        [heap[big], heap[i]] = [heap[i], heap[big]];
        i = big;
      }
    }
    return top;
  };
 
  for (const c in freq) push([freq[c], c]);
  if (heap[0][0] > Math.ceil(s.length / 2)) return ""; // impossible
 
  const result: string[] = [];
  while (heap.length >= 2) {
    const [c1, ch1] = pop();
    const [c2, ch2] = pop();
    result.push(ch1, ch2);
    if (c1 - 1 > 0) push([c1 - 1, ch1]);
    if (c2 - 1 > 0) push([c2 - 1, ch2]);
  }
  if (heap.length === 1) result.push(heap[0][1]); // remaining đơn lẻ
  return result.join("");
}

4.7 Min Arrows to Burst Balloons

// LC #452 — Sort theo END, dùng 1 arrow cho tất cả balloons overlap với "currentEnd".
function findMinArrowShots(points: number[][]): number {
  if (points.length === 0) return 0;
  points.sort((a, b) => a[1] - b[1]);
 
  let arrows = 1;
  let currEnd = points[0][1];
  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > currEnd) {        // không overlap → arrow mới
      arrows++;
      currEnd = points[i][1];
    }
  }
  return arrows;
}

4.8 Queue Reconstruction by Height

// LC #406 — Greedy với 2-key sort tinh tế
// Sort theo h DESC, k ASC → insert vào index k (vì người trước cao hơn hoặc bằng).
function reconstructQueue(people: number[][]): number[][] {
  people.sort((a, b) => b[0] - a[0] || a[1] - b[1]);
  const result: number[][] = [];
  for (const p of people) result.splice(p[1], 0, p);
  return result;
}

5. Complexity Deep-dive

Algorithm	Time	Space	Note
Activity selection	$O (N lo g N)$	$O (1)$	Sort dominates
Jump Game I/II	$O (N)$	$O (1)$	Single pass
Gas Station	$O (N)$	$O (1)$	Single pass + total check
Task Scheduler (formula)	$O (N + 26)$	$O (26)$	Constant alphabet
Reorganize String (heap)	$O (N lo g K)$	$O (K)$	K = unique chars
Min Arrows	$O (N lo g N)$	$O (1)$	Sort dominates
Queue Reconstruction	$O (N^{2})$	$O (N)$	`splice` là $O (N)$

6. Edge Cases & Pitfalls

Pitfall 1: Greedy KHÔNG phải lúc nào cũng đúng

Ví dụ kinh điển: Coin Change với mệnh giá {1, 3, 4} cho amount = 6.

Greedy (lấy lớn nhất trước): 4 + 1 + 1 = 3 coins.

Optimal: 3 + 3 = 2 coins. Greedy fail vì không có greedy choice property. Đây phải dùng DP.

Pitfall 2: Sort theo START hay theo END?

End: bài “max non-overlap intervals”, “min arrows”, “max meetings”.

Start: bài “min meeting rooms” (sweep + heap), “merge intervals”. Nhầm lẫn → sai answer. Test với 2-3 ví dụ trước khi commit.

Pitfall 3: Strict < vs <= trong overlap check

LC #435 (Non-overlapping): intervals[i][0] >= lastEnd — touch ở endpoint OK.

LC #452 (Min Arrows): points[i][0] > currEnd — touch là 1 arrow xuyên cả 2. Mỗi bài có convention riêng — đọc kỹ “is endpoint touching considered overlap?”

Pitfall 4: Heap-based greedy quên repush

Trong Reorganize String, sau khi dùng 2 char top, phải push lại (với count-1) sau khi đã pop cả 2, không trước. Push trước → có thể pick lại ngay → 2 char giống nhau kề nhau.

Pitfall 5: "Greedy bằng feeling"

Trong interview, sau khi propose greedy, luôn kèm 1 câu “I claim greedy is correct because [exchange argument / stays ahead]” và sketch lý do. Interviewer L5+ sẽ trừ điểm nếu bạn skip step này.

7. Pattern Recognition

Mô tả bài toán	Pattern Greedy
”Max số intervals không overlap”	Sort by end, sweep
”Min số arrows / xe / phòng”	Sort + sweep hoặc heap
”Min coins / steps đến đích”	Có thể greedy nhưng test cẩn thận; nhiều khi là DP
”Reorganize / scheduling tasks”	Heap-based greedy
”Connect ropes / huffman”	Min-heap, lặp pop 2 push 1
”Stock buy/sell unlimited” (LC #122)	Sum of positive diffs
”Stock buy/sell with cooldown / fee”	DP, không phải pure greedy
”Container Most Water” (LC #11)	Two-pointer greedy
”Candy distribution” (LC #135)	2-pass greedy (left → right, right → left)

8. Top 12 Problems (priority)

#	LC	Bài	Mức
1	LC-55	Jump Game I	Easy-Medium
2	LC-45	Jump Game II	Medium
3	LC-134	Gas Station	Medium
4	LC-435	Non-overlapping Intervals	Medium
5	LC-452	Min Arrows to Burst Balloons	Medium
6	LC-621	Task Scheduler	Medium
7	LC-767	Reorganize String	Medium
8	LC-122	Best Time Buy Sell II	Easy
9	LC-11	Container Most Water	Medium
10	LC-135	Candy	Hard
11	LC-406	Queue Reconstruction	Medium
12	LC-1647	Min Deletions Unique Frequencies	Medium

9. Self-Assessment Checklist

Tôi có thể giải thích exchange argument trên LC #435.
Tôi biết tại sao Coin Change {1,3,4} không greedy được.
Tôi phân biệt được sort-by-start vs sort-by-end.
Tôi giải Jump Game II không nhìn template trong 10 phút.
Tôi giải thích được công thức Task Scheduler (frame + tail).
Tôi nhận ra heap-based greedy trong Reorganize String trong < 30 giây.
Tôi tự tin propose “greedy” với justification, không “feeling-based”.

Nguyên tắc vàng

Mỗi greedy proposal phải kèm 1-line proof. Không proof = không pass L5+ interview, dù code chạy đúng test.

lthieu's notes

Explorer

14-Greedy

Buổi 14 — Greedy Algorithms

1. Analogy & Context

Greedy: Người leo núi cận thị

Khác biệt với DP

2. The FAANG Standard

L4 vs L5 expectation

3. Decision Tree — Khi nào Greedy?

4. TypeScript Templates

4.1 Activity Selection / Interval Scheduling Maximization

4.2 Jump Game I — Reach the End

4.3 Jump Game II — Min Jumps

4.4 Gas Station — Circular Tour

4.5 Task Scheduler

4.6 Reorganize String

4.7 Min Arrows to Burst Balloons

4.8 Queue Reconstruction by Height

5. Complexity Deep-dive

6. Edge Cases & Pitfalls

7. Pattern Recognition

8. Top 12 Problems (priority)

9. Self-Assessment Checklist

Graph View

Table of Contents

Backlinks