โปรแกรมหาจำนวนแพ็กเกจสูงสุดที่ขายได้ให้ผู้ซื้อใน C++

มีรายการขาย sales=[[day,price]] และผู้ซื้อ buyers=[[payday,amount]] ผู้ซื้อซื้อได้สูงสุด 1 ชิ้น แพ็กเกจขายได้ 1 คน หาจำนวนแพ็กเกจขายได้สูงสุด

ตัวอย่าง: sales=[[0,5],[0,5],[0,6],[1,4],[1,5],[3,4]], buyers=[[0,4],[0,6],[1,5]] → 3

ขั้นตอนการแก้ปัญหา

1. เรียง buyers ตาม payday แล้ว amount
2. เรียง sales ตาม day แล้ว price
3. ใช้ Multiset เก็บ amount ของผู้ซื้อที่ payday <= day ปัจจุบัน
4. วน sales: เพิ่ม buyer ที่เข้ามาได้ → หา lower_bound(price) ใน multiset → เจอ: ขายได้++ ลบออกจาก multiset

ตัวอย่างโค้ด 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 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 << (new Solution())->solve(sales, buyers); // 3
    return 0;
}

อินพุต

sales={{0,5},{0,5},{0,6},{1,4},{1,5},{3,4}}, buyers={{0,4},{0,6},{1,5}}

เอาต์พุต

3