Assign Cookies

Q: Độ phức tạp thời gian của Assign Cookies là gì?

Việc sắp xếp hai mảng tốn O(n log n + m log m) , còn việc duyệt bằng hai con trỏ sau đó tốn O(n + m) , nên phần sắp xếp chiếm ưu thế. Sắp xếp tại chỗ giữ cho bộ nhớ phụ ở mức O(1) , không tính phần bộ nhớ mà chính thuật toán sắp xếp sử dụng.

Q: Tại sao lựa chọn tham lam lại hiệu quả với bài toán Phân phát bánh quy?

Gọi k là chiếc bánh quy nhỏ nhất vừa với đứa trẻ ít tham ăn nhất, và giả sử một cách phân chia tối ưu cho đứa trẻ đó một chiếc bánh quy khác. Hãy đổi: đứa trẻ nhận k , còn người đang giữ k nhận chiếc bánh quy kia, vốn có kích thước ít nhất bằng k , nên cả hai vẫn có bánh ăn. Số lượng không đổi, và ta lặp lại lập luận này cho những đứa trẻ còn lại.

DễTham lam Sắp xếp

+10

Mỗi trẻ i có mức độ tham ăn g[i]: kích thước bánh quy nhỏ nhất khiến trẻ hài lòng. Mỗi chiếc bánh quy j có kích thước s[j]. Một trẻ hài lòng khi nhận được một chiếc bánh quy có kích thước ít nhất bằng mức độ tham ăn của trẻ. Mỗi trẻ nhận tối đa một chiếc bánh quy và mỗi chiếc bánh quy được đưa cho tối đa một trẻ. Hãy trả về số trẻ nhiều nhất mà bạn có thể làm cho hài lòng.

Hàm

findContentChildren(g: integer-array, s: integer-array) → integer

ginteger-array: mức độ tham lam của mỗi đứa trẻ, kích thước bánh quy nhỏ nhất mà chúng chấp nhận
sinteger-array: kích thước của mỗi cookie
Trả vềinteger: số trẻ em nhiều nhất mà mỗi trẻ có thể nhận được một chiếc bánh quy có kích thước ít nhất bằng mức độ tham lam của mình

Ràng buộc

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
Hai mảng có thể có độ dài khác nhau và cả hai đều không được sắp xếp.

Ví dụ

Đầu vào: g = [4, 2, 7]s = [3, 5, 1, 2]
Đầu ra: 2
Giải thích: Sau khi sắp xếp, các em muốn 2, 4 và 7. Chiếc bánh quy 2 được đưa cho em muốn 2, còn chiếc bánh quy 5 được đưa cho em muốn 4. Không chiếc bánh quy nào đến được với em muốn 7, nên đáp án là 2.

Câu hỏi mở rộng

Nếu mỗi đứa trẻ cũng có kích thước bánh quy lớn nhất mà chúng chấp nhận, vậy mỗi chiếc bánh quy chỉ phù hợp với một khoảng kích thước thì sao? Khi đó, nên đưa mỗi chiếc bánh quy cho đứa trẻ nào đang chờ?

Lời giải

Thử ghép từng trẻ với từng chiếc bánh sẽ khiến số trường hợp tăng vọt, nhưng một quy tắc tham lam giải quyết được vấn đề: cho đứa trẻ ít tham ăn nhất ăn trước, bằng chiếc bánh nhỏ nhất phù hợp. Sau khi sắp xếp cả hai mảng, ta chỉ cần duyệt qua chúng một lượt bằng hai con trỏ.

Chiếc bánh quy nhỏ nhất vừa với từng đứa trẻ

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Sắp xếp các em nhỏ từ ít tham ăn nhất đến tham ăn nhất, rồi đưa cho mỗi em chiếc bánh quy nhỏ nhất chưa dùng mà vẫn đủ lớn. Chiếc bánh quy lớn hơn có thể làm no bất kỳ em nào mà chiếc nhỏ hơn có thể làm no, vì vậy đưa chiếc nhỏ nhất phù hợp sẽ giữ lại những chiếc lớn hơn cho các em tham ăn hơn ở phía sau.

Mỗi trong số n em nhỏ quét qua tất cả m chiếc bánh quy: với n = m = 5000, có 25 triệu lần kiểm tra.

Thuật toán

Sắp xếp các hệ số tham lam theo thứ tự từ nhỏ đến lớn.
Đánh dấu từng chiếc bánh quy để biết nó đã được dùng hay chưa.
Với mỗi đứa trẻ, kiểm tra tất cả bánh quy và ghi nhớ chiếc nhỏ nhất chưa dùng có kích thước ít nhất bằng mức độ tham lam của đứa trẻ.
Nếu tìm thấy một chiếc, đánh dấu chiếc đó đã được dùng và tính đứa trẻ là hài lòng.
Trả về số lượng.

def findContentChildren(g, s):
    used = [False] * len(s)
    fed = 0
    for need in sorted(g):  # least greedy child first
        best = -1
        for j in range(len(s)):
            if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
                best = j
        if best != -1:
            used[best] = True
            fed += 1
    return fed

Sắp xếp cả hai rồi dùng hai con trỏ

Ý tưởng

Sắp xếp cả bánh quy, rồi bạn sẽ gặp chiếc bánh quy vừa đủ nhỏ nhất trước tiên. Duyệt bánh quy từ nhỏ đến lớn bằng một con trỏ, child, trỏ đến đứa trẻ ít tham ăn nhất vẫn đang chờ. Chiếc bánh quy có kích thước ít nhất là g[child] sẽ khiến đứa trẻ đó no và con trỏ tiến lên. Chiếc bánh quy nhỏ hơn cũng nhỏ hơn mức tham ăn của mọi đứa trẻ đang chờ, nên không có ích gì.

Trong ví dụ đầu tiên, bánh quy 1 quá nhỏ so với mức 2, bánh quy 2 khiến đứa trẻ muốn mức 2 no, bánh quy 3 quá nhỏ so với mức 4, còn bánh quy 5 khiến đứa trẻ muốn mức 4 no. Con trỏ dừng ở vị trí 2.

Mỗi con trỏ chỉ di chuyển về phía trước, nên quá trình duyệt có độ phức tạp O(n + m), còn hai lần sắp xếp chiếm phần lớn thời gian.

Thuật toán

Sắp xếp g và s theo thứ tự tăng dần.
Đặt child = 0, ứng với đứa trẻ ít tham ăn nhất vẫn đang chờ.
Với mỗi chiếc bánh quy, bắt đầu từ chiếc nhỏ nhất: nếu child vẫn nằm trong g và chiếc bánh quy có kích thước ít nhất bằng g[child], hãy tăng child thêm 1.
Trả về child, số trẻ đã được cho ăn.

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = 0  # the least greedy child still waiting
    for size in s:  # smallest cookie first
        if child < len(g) and size >= g[child]:
            child += 1
    return child

Lỗi thường gặp và trường hợp biên

Đưa cho một đứa trẻ chiếc bánh quy lớn hơn mức cần thiết. Với g = [1, 2] và s = [1, 3], đưa chiếc bánh quy 3 cho đứa trẻ muốn chiếc bánh quy kích thước 1 sẽ khiến đứa trẻ muốn kích thước 2 vẫn đói.
Tăng chỉ số của đứa trẻ khi chiếc bánh quy quá nhỏ. Đứa trẻ vẫn cần bánh quy, chiếc bánh quy mới là thứ không dùng được.
Bỏ qua bước kiểm tra giới hạn của chỉ số đứa trẻ. Với g = [1] và s = [1, 2], chiếc bánh quy 2 khiến chương trình đọc vượt quá cuối g.
So sánh bằng > thay vì ≥. Chiếc bánh quy có kích thước đúng bằng mức độ tham ăn là đủ.
Sắp xếp số như văn bản. Trong JavaScript, sort() không có hàm so sánh sẽ đặt 10 trước 9.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Assign Cookies là gì?

Việc sắp xếp hai mảng tốn O(n log n + m log m), còn việc duyệt bằng hai con trỏ sau đó tốn O(n + m), nên phần sắp xếp chiếm ưu thế. Sắp xếp tại chỗ giữ cho bộ nhớ phụ ở mức O(1), không tính phần bộ nhớ mà chính thuật toán sắp xếp sử dụng.

Tại sao lựa chọn tham lam lại hiệu quả với bài toán Phân phát bánh quy?

Gọi k là chiếc bánh quy nhỏ nhất vừa với đứa trẻ ít tham ăn nhất, và giả sử một cách phân chia tối ưu cho đứa trẻ đó một chiếc bánh quy khác. Hãy đổi: đứa trẻ nhận k, còn người đang giữ k nhận chiếc bánh quy kia, vốn có kích thước ít nhất bằng k, nên cả hai vẫn có bánh ăn. Số lượng không đổi, và ta lặp lại lập luận này cho những đứa trẻ còn lại.

Bạn có thể bắt đầu từ đứa trẻ tham ăn nhất thay vào đó không?

Đúng vậy. Hãy sắp xếp cả hai mảng rồi duyệt từ chiếc bánh quy lớn nhất và đứa trẻ tham ăn nhất. Nếu chiếc bánh quy lớn nhất còn lại phù hợp với đứa trẻ tham ăn nhất còn lại, hãy cho trẻ đó ăn rồi di chuyển cả hai con trỏ; nếu không, sẽ không có chiếc bánh quy nào cho trẻ đó ăn được, vậy nên hãy bỏ qua trẻ đó. Cách này cho ra cùng số lượng trong cùng khoảng thời gian.

def findContentChildren(g, s):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

g = [4, 2, 7]
s = [3, 5, 1, 2]

Đầu ra mong đợi