A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti],&nbsp;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.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

&nbsp;
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.


Example 2:

Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859


Example 3:

Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086


&nbsp;
Constraints:


	2 * n == costs.length
	2 &lt;= costs.length &lt;= 100
	costs.length is even.
	1 &lt;= aCosti, bCosti &lt;= 1000


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n = len(costs)
        m = n // 2
        
        @lru_cache(None)
        def dfs(cur, a):
			# cur is the current user index
			# `a` is the number of people travel to city `a`
			
            if cur == n:
                return 0
            
			# people to b city
            b = cur - a
            ans = float('inf')
            
			# the number of people to `a` city number did not reach to limit, 
			# then current user can trval to city `a`
			
            if a < m:
                ans = min(dfs(cur+1, a+1)+costs[cur][0], ans)
            
			# the number of people to `b` city number did not reach to limit
			# then current user can trval to city `b`
            if b < m:
                ans = min(dfs(cur+1, a)+costs[cur][1], ans)
                
            return ans
        
        return dfs(0, 0)
// costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
//  The difference between them would be like this [511,  -394, -259, -45, -722, -108]  this will give us the differnce c[1] - c[0]
// Now after sorting them from highest to smallest would be [511, -45, -108, -259, -394,-722] from high to low c2[1] - c2[0], c1[1] - c1[0]  if we want low to high then it would be like this c1[1] - c1[0], c2[1] - c2[0]
// 

class Solution {
    public int twoCitySchedCost(int[][] costs) {
       Arrays.sort(costs, (c1, c2) -> Integer.compare(c2[1] - c2[0], c1[1] - c1[0]));// biggest to smallest
        int minCost = 0;               
        int n = costs.length;
        for (int i = 0; i < n; i++) {
            minCost += i < n/2? costs[i][0] : costs[i][1];//First half -> A; Last half -> B  259 + 184 + 577 + 54 + 667 + 118
        }
        return minCost;
    }
}
class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](const vector<int> &curr, const vector<int> &next){ // CUSTOM COMPARATOR
            return (curr[0]-curr[1]) < (next[0]-next[1]);   // (comparing cost of sending to A - cost to B)
        });
        // original:   [[10,20],[30,200],[400,50],[30,20]] 
        // after sort: [[30,200],[10,20],[30,20],[400,50]]
        // to do:         a       a          b         b
        
        int sum = 0;
        for(int i=0; i<costs.size()/2; i++){
            sum+=costs[i][0];
            // cout<<costs[i][0]<<" "; // 30 10
        }
        for(int i=costs.size()/2; i<costs.size(); i++){
            sum+=costs[i][1];
            // cout<<costs[i][1]<<" "; // 20 50
        }
        
        return sum;
    }
};
/**
 * @param {number[][]} costs
 * @return {number}
 */
var twoCitySchedCost = function(costs) {
    // TC: O(nlogn) and O(1) extra space
    let n=costs.length;
    let countA=0,countB=0,minCost=0;
    
    // sorted in descending order by their absolute diff
    costs=costs.sort((a,b)=>{
        let diffA=Math.abs(a[0] - a[1]);
        let diffB=Math.abs(b[0] - b[1]);
        return diffB-diffA;
    });
    
    for(let i=0;i<n;i++){
        let [a,b]=costs[i];
        if(a<b){
            if(countA<n/2){
                minCost+=a;
                countA++;
            }else{
                minCost+=b;
                countB++;
            }
        }else{
            if(countB<n/2){
                minCost+=b;
                countB++;
            }else{
                minCost+=a;
                countA++;
            }
        }
    }
    return minCost;
};
Two City Scheduling