#include <bits/stdc++.h>
using namespace std;

/*
  Problem 1029. Two City Scheduling
  
  A company is planning to interview 2n people. Given the array costs
  where costs[i] = [aCost_i, bCost_i], the cost of flying the ith person
  to city a is aCost_i, and the cost of flying the ith person to city b
  is bCost_i.
  
  Return the minimum cost to fly every person to a city such that
  exactly n people arrive in each city.

  Example 1:

  Input: costs = [[10,20],[30,200],[400,50],[30,20]]
  Output: 110
  Explanation: 
  The first person goes to city A for a cost of 10.
  The second person goes to city A for a cost of 30.
  The third person goes to city B for a cost of 50.
  The fourth person goes to city B for a cost of 20.
  
  The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.  
*/

void printCosts(const char* label, vector<vector<int>> v)
{
    cout << label << "[";
    for (auto i: v)
    {
        cout << "[";            
        for (int j = 0; j < (int)i.size(); j++)
        {
            cout << i.at(j);
            if (j < (int)i.size() - 1) cout << ",";
        }
        cout << "]";            
    }
    cout << "]\ndiffs: ";
    for (auto i: v)
    {
        for (int j = 0; j < (int)i.size() - 1; j++)
        {
            cout << i.at(j) - i.at(j+1) << " ";            
        }
    }
    cout << endl;    
}


// sort by absolute diff between the values
struct compareCosts
{
    bool operator()(vector<int> a, vector<int> b) const
    {
        // sort by diff between [aCost_i, bCost_i]
        return a.at(0) - a.at(1) < b.at(0) - b.at(1);
    }
};
//compareCosts;

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int cost = 0;        

        cout << "costs size: " << costs.size() << endl;
        
        sort(costs.begin(), costs.end(),
             [](vector<int> a, vector<int> b)
             {
                 // sort ascending by diff between [aCost_i, bCost_i]
                 return a.at(0) - a.at(1) < b.at(0) - b.at(1);
             });
             
        printCosts("sorted costs: ", costs);

        for (size_t i = 0; i < costs.size(); i++)
        {            
            if (i < costs.size()/2) // first half sum a_i costs
                                    // second half sum b_i costs
                cost += costs.at(i).at(0); // a_i
            else
                cost += costs.at(i).at(1); // b_i
        }        
        return cost;
    }
};

int main()
{
    vector<pair<vector<vector<int>>,int>> testCases = {
        {{{10,20},{30,200},{400,50},{30,20}},110},
// diff     -10     -170     350       10    ===> sort by diff between [aCost_i, bCost_i]
        {{{259,770},{448,54},{926,667},{184,139},{840,118},{577,469}},1859},
        {{{515,563},{451,713},{537,709},{343,819},{855,779},{457,60},{650,359},{631,42}},3086},
    };

    for (auto& tc: testCases)
    {
        Solution s;
        vector<vector<int>> costs = tc.first;
        int result = s.twoCitySchedCost(costs);
        cout << "   input: [";
        for (auto i: costs)
        {
            cout << "[";            
            for (int j = 0; j < (int)i.size(); j++)
            {
                cout << i.at(j);
                if (j < (int)i.size() - 1) cout << ",";
            }
            cout << "]";            
        }
        cout << "]\n";        
        cout << "  output: " << result << endl;
        cout << "expected: " << tc.second << endl;
        cout << "-------------------\n";
    }    
}