Chương 16 - Greedy

Greedy = tham lam = mỗi bước chọn cái tốt nhất tại chỗ, hy vọng cộng dồn lại được kết quả tối ưu toàn cục. Pattern lừa dối ở chỗ: Greedy hợp lệ rất khó chứng minh. Trong phỏng vấn, bạn vừa phải đoán đúng “luật tham” vừa phải justify ngắn gọn vì sao nó tối ưu. Chương này dạy 6 bài kinh điển - học để có mẫu reasoning.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Học proof framework: exchange argument, stay-ahead, cut property.
  • Biết khi greedy SAI → chuyển sang DP.
  • Pattern “farthest reach” cho Jump Game family.
  • Pattern 2-pass cho Candy (left-to-right + right-to-left).

Khi nào dùng pattern này?

  • Đề bài hỏi tối ưu (max/min) và có tính chất “exchange argument”: nếu có nghiệm khác, ta luôn có thể “hoán đổi” sang nghiệm greedy mà không tệ hơn.
  • Có lựa chọn rõ ràng tại mỗi bước mà không cần xem toàn cục (≠ DP).
  • Bài thường có dạng: sort theo X rồi quét tuyến tính.

Trick chứng minh Greedy: 1. Exchange argument: giả sử có nghiệm tối ưu khác greedy, “hoán đổi” để biến nó thành greedy mà không xấu đi. 2. Cấu trúc matroid: ít gặp trong phỏng vấn nhưng đẹp về lý thuyết.

Khi Greedy sai → DP cứu: nếu hoán đổi không bảo toàn tối ưu, phải xét toàn cục → DP.

Template code 

def greedy_template(items):
    items.sort(key=...)         # 90% bài greedy phải sort trước
    result = 0
    for x in items:
        if local_condition(x):
            result += x
            # ... cập nhật state ...
    return result

Bài tự luyện cuối chương

  • LC 122 - Best Time to Buy and Sell Stock II
  • LC 376 - Wiggle Subsequence
  • LC 406 - Queue Reconstruction by Height
  • LC 435 - Non-overlapping Intervals (Chương 14)
  • LC 452 - Minimum Number of Arrows to Burst Balloons (Chương 14)
  • LC 678 - Valid Parenthesis String
  • LC 870 - Advantage Shuffle

16.1 Jump Game (LC 55)

Đề bài

Cho mảng nums, nums[i] = số bước tối đa bạn có thể nhảy từ vị trí i. Bắt đầu ở i = 0. Trả về True nếu có thể tới i = n - 1.

Ví dụ 

Input:  nums = [2, 3, 1, 1, 4]   → True
Giải thích: 0 → 1 → 4 hoặc 0 → 2 → 3 → 4

Input:  nums = [3, 2, 1, 0, 4]   → False
Giải thích: tới index 3 thì kẹt (nums[3]=0).

Ràng buộc

  • 1 <= len(nums) <= 10^4
  • 0 <= nums[i] <= 10^5

Clarifying questions

  • Có thể đứng yên? → Không.
  • nums[0] = 0? → Chỉ thắng nếu n == 1.

Hướng tiếp cận

Brute force - DFS từ 0, O(2^n). TLE.

Tối ưu - Greedy 1 lượt, O(n).

Duy trì farthest = vị trí xa nhất có thể tới đến bây giờ. Tại mỗi i: - Nếu i > farthest → không tới được i → return False. - Cập nhật farthest = max(farthest, i + nums[i]). - Nếu farthest >= n - 1 → return True.

Hình minh hoạ với [2, 3, 1, 1, 4]:

index :   0   1   2   3   4
nums  :   2   3   1   1   4

i=0: farthest = max(0, 0+2) = 2
i=1: 1 <= 2 OK; farthest = max(2, 1+3) = 4 → >= n-1=4 → True ✓

Code Python 3 

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0
        for i, x in enumerate(nums):
            if i > farthest:
                return False
            farthest = max(farthest, i + x)
            if farthest >= len(nums) - 1:
                return True
        return True

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

  • Greedy justification: Nếu farthest >= n - 1 → có một chuỗi nhảy tới đích. Nếu i > farthest → mọi vị trí ≤ i đều không tới i → impossible.
  • Bẫy: dùng >= thay vì > ở check i > farthest - chính xác farthest là tới được (bao gồm).

Bài tự luyện liên quan

  • LC 45 - Jump Game II (bài 16.2).
  • LC 1306 - Jump Game III.

16.2 Jump Game II (LC 45)

Đề bài

Cùng thiết lập như 16.1, nhưng giả sử luôn tới được n - 1. Trả về số bước nhảy tối thiểu.

Ví dụ 

Input:  nums = [2, 3, 1, 1, 4]
Output: 2
Giải thích: 0 → 1 → 4.

Input:  nums = [2, 3, 0, 1, 4]
Output: 2

Ràng buộc

  • 1 <= len(nums) <= 10^4
  • 0 <= nums[i] <= 1000
  • Luôn tới được index cuối

Clarifying questions

  • n = 1? → Trả 0 (đã ở đích).
  • nums[i] = 0 ở giữa? → OK miễn tới được cuối.

Hướng tiếp cận

BFS theo lớp. Mỗi “level” của BFS = các vị trí có thể tới sau k bước.

Implementation Greedy 1 lượt: - current_end = ranh giới của level hiện tại. - farthest = xa nhất tới được trong level hiện tại. - Khi i == current_end (kết thúc level), bump jumps += 1 và set current_end = farthest.

Hình minh hoạ với [2, 3, 1, 1, 4]:

i=0:  farthest = max(0, 0+2) = 2
      i == current_end (=0) → jumps=1, current_end=2
i=1:  farthest = max(2, 1+3) = 4
i=2:  farthest = max(4, 2+1) = 4
      i == current_end (=2) → jumps=2, current_end=4
i=3:  ... (đã quá đủ, ta dừng khi current_end >= n-1)

Đáp án: 2  ✓

Code Python 3 

from typing import List

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        current_end = 0
        farthest = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == current_end:
                jumps += 1
                current_end = farthest
                if current_end >= len(nums) - 1:
                    break
        return jumps

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

  • Loop chỉ tới n - 1 (không inclusive) - vì khi ở n-1 không cần nhảy nữa.
  • Pattern “implicit BFS”: thay vì queue thật, ta dùng 2 con trỏ current_end và farthest.

Bài tự luyện liên quan

  • LC 55 - Jump Game.
  • LC 1306 - Jump Game III.
  • LC 1345 - Jump Game IV.

16.3 Gas Station (LC 134)

Đề bài

Có n trạm xăng vòng tròn, trạm i có gas[i] xăng. Đi từ trạm i tới i+1 tốn cost[i]. Tìm chỉ số trạm bắt đầu sao cho đi hết vòng được, hoặc -1 nếu không thể.

Ví dụ 

Input:  gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Giải thích: bắt đầu từ trạm 3.

Input:  gas = [2,3,4], cost = [3,4,3]
Output: -1

Ràng buộc

  • 1 <= n <= 10^5

Clarifying questions

  • Tổng gas < tổng cost? → Không thể đi vòng → -1.
  • Bắt đầu từ index nào nếu nhiều answer hợp lệ? → Theo đề duy nhất 1 answer.

Hướng tiếp cận

Brute force - thử mỗi start, O(n²). Có thể TLE.

Tối ưu Greedy - O(n).

Điều kiện cần & đủ: sum(gas) >= sum(cost). Nếu vi phạm → -1.

Khi điều kiện thoả, chỉ tồn tại đúng 1 nghiệm (nếu mảng phân biệt). Tìm bằng: - Duyệt, giữ tank = balance hiện tại. - Nếu tank < 0 tại trạm i → mọi start ∈ [last_start..i] đều fail. Set start = i + 1, reset tank = 0.

Hình minh hoạ với gas = [1,2,3,4,5], cost = [3,4,5,1,2]:

i :    0     1     2     3     4
gas:   1     2     3     4     5
cost:  3     4     5     1     2
diff: -2    -2    -2    +3    +3

tank tích luỹ:
  i=0: tank = -2 → negative, reset start=1, tank=0
  i=1: tank = -2 → reset start=2, tank=0
  i=2: tank = -2 → reset start=3, tank=0
  i=3: tank = +3 OK
  i=4: tank = +6 OK

sum(diff) = -2-2-2+3+3 = 0 >= 0 → có nghiệm.
Đáp án: start=3 ✓

Code Python 3 

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        start = 0
        tank = 0
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0:
                start = i + 1
                tank = 0
        return start

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

  • Greedy justification: Giả sử start là s và đi đến i thì tank âm. Mọi s' ∈ [s, i] cũng sẽ âm tại i (vì sum từ s' đến i ≤ sum từ s đến i). Vậy ta bỏ hết [s, i] và thử i + 1.
  • Bẫy: quên check sum(gas) < sum(cost) - nếu không, code trả về start vẫn không hợp lệ.

Bài tự luyện liên quan

  • LC 871 - Minimum Number of Refueling Stops (heap-based greedy).
  • LC 134 - Gas Station.

16.4 Assign Cookies (LC 455)

Đề bài

Cho mảng g[] (greed factor của trẻ) và s[] (size của cookie). Trẻ i hài lòng nếu nhận được cookie j với s[j] >= g[i]. Mỗi trẻ tối đa 1 cookie, mỗi cookie tối đa 1 trẻ. Tìm max số trẻ hài lòng.

Ví dụ 

Input:  g = [1, 2, 3], s = [1, 1]   → 1
Input:  g = [1, 2], s = [1, 2, 3]   → 2

Ràng buộc

  • 1 <= g.length <= 3·10^4
  • 0 <= s.length <= 3·10^4
  • 1 <= g[i], s[j] <= 2^31-1

Clarifying questions

  • Cookie hoặc trẻ list rỗng? → Trả 0.
  • Một cookie cho nhiều trẻ? → Không, mỗi cookie ≤ 1 trẻ.

Hướng tiếp cận

Greedy kinh điển. Sort cả 2 mảng tăng dần. Two pointers i (trẻ), j (cookie). Đi qua cookie từ nhỏ đến lớn: nếu s[j] >= g[i] → trẻ i được cookie → i++; j++ luôn.

Justification: Đưa cookie nhỏ nhất đủ thoả cho trẻ greed nhỏ nhất - không “phí” cookie lớn. Exchange argument: nếu nghiệm tối ưu khác greedy, có thể đổi cookie giữa 2 trẻ mà không xấu đi.

Code Python 3 

from typing import List

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i = j = 0
        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                i += 1
            j += 1
        return i

Phân tích độ phức tạp

  • Thời gian: O(n log n + m log m). Bộ nhớ: O(1).

Bình luận

  • Một biến thể khác: sort giảm dần (cookie lớn nhất cho trẻ greed lớn nhất). Cùng kết quả.

Bài tự luyện liên quan

  • LC 870 - Advantage Shuffle (cùng pattern matching).

16.5 Partition Labels (LC 763)

Đề bài

Cho chuỗi s. Chia s thành nhiều phần tối đa sao cho mỗi ký tự chỉ xuất hiện trong đúng 1 phần. Trả về độ dài của các phần.

Ví dụ 

Input:  s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
Giải thích:
  "ababcbaca" - chứa a, b, c.
  "defegde"   - chứa d, e, f, g.
  "hijhklij"  - chứa h, i, j, k, l.

Ràng buộc

  • 1 <= len(s) <= 500
  • s chỉ chứa chữ thường

Clarifying questions

  • Chuỗi rỗng? → Trả [].
  • Chỉ 1 ký tự xuất hiện? → Vẫn cần phân partition.

Hướng tiếp cận

Greedy với “last occurrence”:

  1. Tìm last[ch] = chỉ số cuối của mỗi ký tự.
  2. Duyệt s, giữ end = max(end, last[s[i]]).
    • Nếu i == end → kết thúc 1 phần.

Hình minh hoạ với "ababcbacadefegdehijhklij":

last[a]=8, last[b]=5, last[c]=7, last[d]=14, last[e]=15, ...

i=0 (a): end = max(0, 8) = 8
i=1 (b): end = max(8, 5) = 8
...
i=8 (a): end = 8, i == end → phần 1: length 9 (0..8)
i=9 (d): end = 14
...
i=15 (e): end = 15, i == end → phần 2: length 7 (9..15)
...

Code Python 3 

from typing import List

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {ch: i for i, ch in enumerate(s)}
        result: list[int] = []
        start = end = 0
        for i, ch in enumerate(s):
            end = max(end, last[ch])
            if i == end:
                result.append(i - start + 1)
                start = i + 1
        return result

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1) (bảng chữ 26).

Bình luận

  • Greedy justification: mỗi phần phải bao gồm last occurrence của tất cả ký tự đã xuất hiện trong đó. Chính end chính là last occurrence này.

Bài tự luyện liên quan

  • LC 56 - Merge Intervals (cùng tinh thần “tới end của max”).
  • LC 1024 - Video Stitching.

16.6 Candy (LC 135)

Đề bài

Cho mảng ratings. Phát kẹo cho n trẻ sao cho: 1. Mỗi trẻ ít nhất 1 kẹo. 2. Trẻ có rating cao hơn người hàng xóm (kề bên) thì được nhiều kẹo hơn.

Trả về số kẹo tối thiểu.

Ví dụ 

Input:  ratings = [1, 0, 2]   → 5    (kẹo: [2, 1, 2])
Input:  ratings = [1, 2, 2]   → 4    (kẹo: [1, 2, 1])

Ràng buộc

  • 1 <= len(ratings) <= 2·10^4
  • 0 <= ratings[i] <= 2·10^4

Clarifying questions

  • n = 1? → Mỗi trẻ tối thiểu 1 → trả 1.

Hướng tiếp cận

2 lượt qua mảng: - Lượt 1 (trái → phải): nếu ratings[i] > ratings[i-1] → candies[i] = candies[i-1] + 1. - Lượt 2 (phải → trái): nếu ratings[i] > ratings[i+1] → candies[i] = max(candies[i], candies[i+1] + 1).

Tổng candies = đáp án.

Hình minh hoạ với ratings = [1, 0, 2]:

ratings:    1   0   2

Lượt 1 (L→R), khởi tạo candies = [1, 1, 1]:
  i=1: r[1]=0 <= r[0]=1 → giữ 1
  i=2: r[2]=2 > r[1]=0  → candies[2] = candies[1]+1 = 2
  → candies = [1, 1, 2]

Lượt 2 (R→L):
  i=1: r[1]=0 <= r[2]=2 → giữ
  i=0: r[0]=1 > r[1]=0  → candies[0] = max(1, candies[1]+1) = max(1, 2) = 2
  → candies = [2, 1, 2]

Tổng: 2 + 1 + 2 = 5  ✓

Code Python 3 

from typing import List

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n
        # Lượt 1.
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
        # Lượt 2.
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
        return sum(candies)

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(n).

Bình luận

  • Tại sao 2 lượt? Ràng buộc trái-phải và phải-trái độc lập với nhau - mỗi lượt thoả 1 chiều. max ở lượt 2 đảm bảo cả 2 ràng buộc cùng thoả.
  • Tối ưu space O(1) có thể nhưng phức tạp (đếm “tăng đoạn” và “giảm đoạn” - xem follow-up).

Bài tự luyện liên quan

  • LC 42 - Trapping Rain Water (cũng dùng 2 lượt L→R, R→L).
  • LC 152 - Maximum Product Subarray (track 2 chiều).

Tóm tắt chương & Quyết định

3 cách “justify greedy” trong phỏng vấn

  1. Exchange argument: Giả sử có lời giải tối ưu khác. Swap 1 lựa chọn của nó về greedy, chỉ ra cost không tăng. Lặp → tối ưu trùng greedy.
  2. Stay-ahead: Tại mọi bước k, lời giải greedy “tiến” ít nhất bằng mọi lời giải khác. Quy nạp → toàn cục tối ưu.
  3. Cut/Matroid property (cho MST, Greedy Choice): mọi đáp số tối ưu chứa được cạnh nhẹ nhất của một cut.

Jump Game (LC 55) - farthest-reach invariant 

i:        0  1  2  3  4
nums:    [2, 3, 1, 1, 4]
reach:    2  4  4  4  ≥4 ✅
  • reach = chỉ số xa nhất đến được tới thời điểm i.
  • Nếu i > reach tại bất kỳ bước nào → kẹt.

Gas Station (LC 134) - vì sao bỏ cả segment failed?

Nếu khởi đầu từ s mà fail tại i (tank âm), thì mọi điểm k trong [s, i] cũng fail khi xuất phát từ k (vì từ s đến k mình đã có dư xăng, vẫn không kéo được tới i+1). ⇒ Tiếp tục thử i+1.

Candy (LC 135) - 2-pass invariant

  • L→R: với mỗi i, nếu rating[i] > rating[i-1] ⇒ candy[i] = candy[i-1] + 1.
  • R→L: nếu rating[i] > rating[i+1] ⇒ candy[i] = max(candy[i], candy[i+1] + 1).
  • 2 ràng buộc cho 2 phía, độc lập ⇒ max đủ.