C++で購入者が購入できるパッケージの最大数を見つけるためのプログラム

販売と購入者の2つのリストがあるとします。 salesの各要素には、[day、price]の形式で2つの値が含まれます。これは、パッケージがその特定の価格でその日にのみ販売可能であることを示します。また、[payday、amount]の形式の購入者の各要素は、購入者が支払い日以降に使用できる金額を持っていることを示します。各購入者が最大で1つのパッケージを購入でき、各パッケージを1人だけに販売できる場合は、購入できるパッケージの最大数を見つけます。

したがって、入力がsales =[[0、5]、[0、5]、[0、6]、[1、4]、[1、5]、[3、4]]の場合、buyers =[[ 0、4]、[0、6]、[1、5]]の場合、最初の人がパッケージ[1、4]を受け取ることができるため、出力は3になります。二人目は[0、6]を取ることができます。そして最後の人はパッケージをとることができます[1、5]。

これを解決するには、次の手順に従います-

• ret：=0

• 給料日が同じ場合は、給料日に基づいてアレイの購入者を並べ替えます。金額で並べ替えます

• セットpqを定義する

• アレイの売上を並べ替える

• i：=0

• アイテムごとに販売中-

  • 一方（i <購入者と購入者のサイズ[i、0] <=it [0]）、実行-

    • Buyers [i、1]をpqに挿入します

    • （iを1増やします）

  • j：=pqのインデックス。それを挿入します[i]intppqそしてソートします

  • jが有効なインデックスである場合、-

    • （retを1増やします）

    • pqからj番目の要素を削除します

• 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