Assign Cookies trong C++

Cho mảng g (ham muốn của trẻ) và mảng s (kích thước bánh). Trẻ i hài lòng nếu nhận bánh size ≥ g[i]. Mỗi trẻ tối đa 1 bánh. Tối đa số trẻ hài lòng.

Ví dụ: g=[1,2], s=[1,2,3] → 2 trẻ hài lòng.

Giải thuật (Tham lam + Sắp xếp)

1. Sắp xếp cả hai mảng tăng dần.
2. Duyệt con trỏ i (trẻ), j (bánh): nếu s[j] ≥ g[i] → i++, j++; ngược lại chỉ j++.
3. Kết quả là i (số trẻ đã phân được bánh).

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0, j = 0;
        while (i < g.size() && j < s.size()) {
            if (g[i] <= s[j]) ++i;
            ++j;
        }
        return i;
    }
};

int main() {
    Solution ob;
    vector<int> g = {1,2}, s = {1,2,3};
    cout << ob.findContentChildren(g, s); // 2
    return 0;
}

Đầu vào / Đầu ra

Input: {1,2}, {1,2,3}
Output: 2