C++ में खरीदारों द्वारा खरीदे जा सकने वाले अधिकतम पैकेज की संख्या ढूंढने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास दो सूचियाँ sales और buyers हैं। sales में प्रत्येक तत्व में दो मान होते हैं [दिन, कीमत] जो दर्शाता है कि पैकेज केवल उस दिन उस दी गई कीमत पर बिक्री के लिए उपलब्ध है। और buyers में प्रत्येक तत्व [पेडे, राशि] के रूप में होता है जो दर्शाता है कि खरीदार के पास पेडे पर और उसके बाद खर्च करने के लिए उतनी राशि है। यदि प्रत्येक खरीदार अधिकतम एक पैकेज खरीद सकता है, और प्रत्येक पैकेज केवल एक व्यक्ति को बेचा जा सकता है, तो खरीदे जा सकने वाले पैकेज की अधिकतम संख्या ढूंढें।

उदाहरण के लिए, यदि इनपुट है sales = [[0, 5], [0, 5], [0, 6], [1, 4], [1, 5], [3, 4]] buyers = [[0, 4], [0, 6], [1, 5]], तो आउटपुट 3 होगा, क्योंकि पहला व्यक्ति पैकेज [1, 4] ले सकता है। दूसरा व्यक्ति [0, 6] ले सकता है। और अंतिम व्यक्ति पैकेज [1, 5] ले सकता है।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

1. ret := 0
2. buyers ऐरे को पेडे के आधार पर सॉर्ट करें, यदि पेडे समान हैं तो राशि के आधार पर सॉर्ट करें
3. एक मल्टीसेट pq परिभाषित करें
4. sales ऐरे को सॉर्ट करें
5. i := 0
6. sales में प्रत्येक आइटम it के लिए:
   • जब तक (i < buyers का आकार और buyers[i][0] <= it[0]):
     • buyers[i][1] को pq में डालें
     • i बढ़ाएं
   • j := pq में it[1] को डालने का इंडेक्स ताकि यह सॉर्टेड रहे
   • यदि j एक वैध इंडेक्स है:
     • ret बढ़ाएं
     • pq से jवां तत्व हटाएं
7. ret वापस करें

उदाहरण

#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);
}

इनपुट

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

आउटपुट

3