Two City Scheduling

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

Find 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

Approach

Java

import java.util.Arrays;
import java.util.Comparator;

public class TwoCityScheduling {
    public static void main(String[] args) {
        int costs[][] = { { 10, 20 }, { 30, 200 }, { 400, 50 }, { 30, 20 } };
        System.out.println(twoCitySchedCost(costs));
    }

    static int twoCitySchedCost(int[][] costs) {
        int n = costs.length;
        int ans = 0;
        int cnt1 = n / 2, cnt2 = n / 2;
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (Math.abs(o1[0] - o1[1]) > Math.abs(o2[0] - o2[1]))
                    return -1;
                else
                    return 1;
            }
        });
        for (int i = 0; i < n; i++) {
            if (cnt2 == 0 || (costs[i][0] < costs[i][1] && cnt1 > 0)) {
                cnt1--;
                ans += costs[i][0];
            } else {
                cnt2--;
                ans += costs[i][1];
            }
        }
        return ans;
    }
}

C++

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

//comparator used to sort the array
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 ans=0;
        int cnt1=n/2,cnt2=n/2;

        sort(costs.begin(),costs.end(),cmp);
        for(int i=0;i<n;i++)
        {
            if(cnt2==0||(costs[i][0]<costs[i][1]&&cnt1>0))
            {
                cnt1--;
                ans+=costs[i][0];
            }
          else
          {
              cnt2--;
             ans+= costs[i][1];
          }
        }
        return ans;
}
int main()
{
    vector<vector<int>>  costs ={{10,20},{30,200},
                                {400,50},{30,20}};
    cout<<twoCitySchedCost(costs);
    return 0;
}