Chương trình tìm số gói tin tối đa người mua có thể mua trong C++

Mô tả bài toán

Cho danh sách sales (mỗi phần tử [day, price]) và buyers (mỗi phần tử [payday, amount]). Mỗi người mua chỉ mua tối đa 1 gói, mỗi gói chỉ bán cho 1 người. Người mua chỉ có thể mua gói có day ≤ payday và price ≤ amount. Tìm số gói bán được tối đa.

Ví dụ: sales = [[0,5],[0,5],[0,6],[1,4],[1,5],[3,4]], buyers = [[0,4],[0,6],[1,5]] → 3.

Giải thuật

1. Sắp xếp buyers theo payday tăng, amount tăng.
2. Sắp xếp sales theo day tăng, price giảm (để ưu tiên giá cao hơn).
3. Duyệt sales, dùng multiset lưu amount của các buyer có payday ≤ day hiện tại.
4. Với mỗi gói tin, tìm trong multiset buyer có amount ≥ price (lower_bound). Nếu tìm thấy, tăng kết quả và xóa buyer đó.

Ví dụ minh họa (C++)

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

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    }
    int solve(vector<vector<int>>& sales, vector<vector<int>>& buyers) {
        int ret = 0;
        sort(buyers.begin(), buyers.end());
        multiset<int> pq;
        sort(sales.begin(), sales.end(), cmp);
        int i = 0;
        for (auto& it : sales) {
            while (i < buyers.size() && buyers[i][0] <= it[0]) {
                pq.insert(buyers[i][1]);
                i++;
            }
            auto j = pq.lower_bound(it[1]);
            if (j != pq.end()) {
                ret++;
                pq.erase(j);
            }
        }
        return ret;
    }
};

int solve(vector<vector<int>>& sales, vector<vector<int>>& buyers) {
    return (new Solution())->solve(sales, buyers);
}

int main() {
    vector<vector<int>> sales = {{0,5},{0,5},{0,6},{1,4},{1,5},{3,4}};
    vector<vector<int>> buyers = {{0,4},{0,6},{1,5}};
    cout << solve(sales, buyers);
    return 0;
}

Đầu vào

{{0,5},{0,5},{0,6},{1,4},{1,5},{3,4}}, {{0,4},{0,6},{1,5}}

Đầu ra

3