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

2つのリスト「sales（販売情報）」と「buyers（購入者情報）」が与えられているとします。sales の各要素は [day, price] という形式で、そのパッケージが指定された日に指定された価格でのみ販売されることを表します。一方、buyers の各要素は [payday, amount] という形式で、その購入者が給料日（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人目の購入者はパッケージ [1, 4] を、2人目は [0, 6] を、3人目は [1, 5] をそれぞれ購入できるためです。

解法のアプローチ

この問題は貪欲法（グリーディ法）を用いて解きます。手順は以下の通りです。

• 結果を格納する変数 ret を 0 で初期化します

• buyers を payday 昇順にソートします。payday が同じ場合は amount でソートします

• multiset 型の集合 pq を定義します

• sales をソートします（日付昇順、同一日なら価格降順）

• i := 0 とします

• sales の各要素 it について以下を繰り返します

  • i が buyers のサイズ未満 かつ buyers[i][0] <= it[0] である間、次を繰り返します

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

    • i を 1 増やします

  • j := pq に it[1] を挿入してもソート順が崩れない位置（lower_bound の結果）とします

  • j が有効な位置であれば

    • ret を 1 増やします

    • pq から j の位置にある要素を削除します

• ret を返します

アルゴリズムのポイント

このアルゴリズムでは、パッケージを販売日順に処理しながら、その時点で購入資格のある購入者（payday が販売日以前の購入者）の所持金を multiset に登録していきます。lower_bound を使うことで、現在のパッケージ価格を支払える購入者のうち最も所持金の少ない人を効率的に特定できます。余裕のある購入者を、後で登場するより高価なパッケージのために取っておけるため、全体のマッチング数を最大化できます。計算量は O((N + M) log(N + M)) 程度に収まります（N は sales のサイズ、M は buyers のサイズ）。

実装例

理解を深めるために、以下の実装を見てみましょう。

#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