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

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• रिट:=0

• सरणी खरीदारों को वेतन-दिवस के आधार पर क्रमबद्ध करें, यदि वेतन-दिवस समान हैं तो उन्हें राशि के आधार पर क्रमबद्ध करें

• एक सेट pq परिभाषित करें

• सरणी बिक्री को क्रमबद्ध करें

• मैं :=0

• बिक्री में प्रत्येक आइटम के लिए -

  • जबकि (i <खरीदारों और खरीदारों का आकार[i, 0] <=it[0]), करते हैं -

    • खरीदारों [i, 1] को pq में डालें

    • (i 1 से बढ़ाएँ)

  • j :=इसे सम्मिलित करने के लिए pq का सूचकांक [i] intp pq और इसे क्रमबद्ध करें

  • यदि j एक मान्य अनुक्रमणिका है, तो -

    • (रिटर्न 1 से बढ़ाएं)

    • pq से jth एलिमेंट हटाएं

• वापसी रिट

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#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