সি++-এ ক্রেতা-বিক্রেতা ম্যাচিং দিয়ে সর্বোচ্চ প্যাকেজ বিক্রয় করার প্রোগ্রাম

সমস্যা বিবরণ

দুটি লিস্ট: sales (দিন, দাম) এবং buyers (পে-দিন, বাজেট)। প্রতিটি ক্রেতা সর্বোচ্চ একটি প্যাকেজ কিনতে পারে, প্রতিটি প্যাকেজ একজনের হাতে বিক্রি হয়। সর্বোচ্চ কতটি প্যাকেজ বিক্রি হতে পারে তা বের করতে হবে।

উদাহরণ: sales = [[0,5],[0,5],[0,6],[1,4],[1,5],[3,4]] buyers = [[0,4],[0,6],[1,5]] আউটপুট: 3

সমাধানের পদ্ধতি

1. buyers-কে পে-দিন ও বাজেট অনুযায়ী সর্ট করুন।
2. sales-কে দিন ও দাম অনুযায়ী সর্ট করুন।
3. মাল্টিসেট (ব্যালেন্সড বিএসটি) ব্যবহার করুন উপলব্ধ ক্রেতাদের বাজেট ট্র্যাক করতে।
4. প্রতিটি সেল আইটেমের জন্য: ঐ দিন পর্যন্ত উপলব্ধ ক্রেতাদের মাল্টিসেটে যোগ করুন।
5. lower_bound(price) দিয়ে সাবচেয়ে কম বাজেটটি খুঁজে বের করুন যা দাম দিতে পারে।
6. পাওয়া গেলে কাউন্ট বাড়ান এবং মাল্টিসেট থেকে মুছে দিন।

উদাহরণ কোড

#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 << solve(sales, buyers);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: sales={{0,5},{0,5},{0,6},{1,4},{1,5},{3,4}}, buyers={{0,4},{0,6},{1,5}}

আউটপুট: 3