C++で解く2都市スケジューリング問題：最小コストでN人ずつ振り分ける貪欲法

問題概要

2N人の人がいるとします。ある会社が面接を実施する予定で、i番目の人を都市Aへ飛行機で移動させる費用が costs[i][0]、都市Bへ移動させる費用が costs[i][1] として与えられています。各都市にちょうどN人ずつ到着するように全員を移動させるとき、合計費用の最小値を求めるのがこの問題の目的です。

入力例

例えば、入力が [[10, 20], [30, 200], [400, 50], [30, 20]] の場合、出力は 110 になります。具体的には、1人目をコスト10で都市Aへ、2人目をコスト30で都市Aへ送り、3人目と4人目はそれぞれコスト50と20で都市Bへ送ります。合計は 10 + 30 + 50 + 20 = 110 となります。

解法のアプローチ

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。重要なポイントは「2都市間のコスト差が大きい人から優先的に割り当てを決める」という点です。コスト差が大きい人を後回しにすると、どちらの都市にも割り当てにくくなり、結果的に高額な費用を支払うリスクが高まるためです。

アルゴリズムの手順

• n を配列のサイズとします。
• a := n / 2、b := n / 2 とします（それぞれ都市A・Bに割り当て可能な残り人数）。
• |costs[i][0] − costs[i][1]| の降順で配列をソートし、答え ans を 0 で初期化します。
• i = 0 から n − 1 まで以下を繰り返します。
  • b == 0、または costs[i][0] ≤ costs[i][1] かつ a > 0 の場合：a を 1 減らし、ans += costs[i][0]
  • それ以外の場合：b を 1 減らし、ans += costs[i][1]
• 最後に ans を返します。

C++での実装例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    static bool cmp(vector<int> a, vector<int> b){
        return abs(a[0] - a[1]) > abs(b[0] - b[1]);
    }
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int n = costs.size();
        int a = n/2;
        int b = n/2;
        sort(costs.begin(), costs.end(), cmp);
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(b == 0 || (costs[i][0] <= costs[i][1] && a > 0)){
                a--;
                ans += costs[i][0];
            } else {
                b--;
                ans += costs[i][1];
            }
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<vector<int>> c = {{10,20},{30,200},{400,50},{30,20}};
    cout << ob.twoCitySchedCost(c);
}

実行結果

入力

[[10,20],[30,200],[400,50],[30,20]]

出力

110

計算量について

このアルゴリズムの時間計算量は O(n log n) です。配列のソートが処理全体を支配するためです。一方、追加のデータ構造を使用しないため、空間計算量は O(1) で済みます。人数が増えても高速に動作する、非常に実用的な解法と言えるでしょう。