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.
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.

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

 
Constraints:

2n == costs.length
2 <= costs.length <= 100
costs.length is even.
1 <= aCosti, bCosti <= 1000

Difficulty: interview

Starter code:

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        dcosts = sorted(costs, key=lambda i: i[0] - i[1])
        n = len(costs) // 2
        acost = sum(c[0] for c in dcosts[:n])
        bcost = sum(c[1] for c in dcosts[n:])
        return acost + bcost

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        # https://leetcode.com/problems/two-city-scheduling/discuss/297143/Python-faster-than-93-28-ms
        # https://leetcode.com/problems/two-city-scheduling/discuss/278944/3-ways-to-solve.
        res = 0
        costs.sort(key = lambda x: x[1]-x[0], reverse = True)
        for i in range(len(costs)//2):
            res += costs[i][0]
        for i in range(len(costs)//2, len(costs)):
            res += costs[i][1]
            
        return res
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        costs.sort(key=lambda x: (x[1]-x[0]), reverse=True)
        print (costs)
        ans=0
        half=len(costs)//2
        for i in range(half):
            ans+= costs[i][0]
        for i in range(half,len(costs)):
            ans+=costs[i][1]
        return ans
            
        



# class Solution {
#     public int twoCitySchedCost(int[][] costs) {
#         int N = costs.length / 2;
#         int[][] dp = new int[N + 1][N + 1];
#         for (int i = 1; i <= N; i++) {
#             dp[i][0] = dp[i - 1][0] + costs[i - 1][0];
#         }
#         for (int j = 1; j <= N; j++) {
#             dp[0][j] = dp[0][j - 1] + costs[j - 1][1];
#         }
#         for (int i = 1; i <= N; i++) {
#             for (int j = 1; j <= N; j++) {
#                 dp[i][j] = Math.min(dp[i - 1][j] + costs[i + j - 1][0], dp[i][j - 1] + costs[i + j - 1][1]);
#             }
#         }
#         return dp[N][N];
#     }
# }


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        N = len(costs) //2
        dp = [[0]*(N+1) for _ in range(N+1)]
        for i in range(1, N+1):
            dp[i][0] = dp[i-1][0] + costs[i-1][0]
        for j in range(1, N+1):
            dp[0][j] = dp[0][j-1] + costs[j-1][1]
        for i in range(1, N+1):
            for j in range(1, N+1):
                dp[i][j] = min(dp[i-1][j] + costs[i+j-1][0],
                              dp[i][j-1] + costs[i+j-1][1])
        for row in dp:
            print(row)
        return dp[N][N]


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        lc = len(costs)
        c = lc//2
        cost1 = 0
        cost2 = 0
        al = c
        bl = c
        for i in range(lc):
            for j in range(i+1, lc):
                if abs(costs[i][0]-costs[i][1]) < abs(costs[j][0]-costs[j][1]):
                    costs[i], costs[j] = costs[j], costs[i]
        
        for i in range(lc):
            if (costs[i][0] <= costs[i][1] and al>0) or bl==0:
                cost1 += costs[i][0]
                al -= 1
            elif bl>0:
                cost1 += costs[i][1]
                bl -= 1
        al = c
        bl = c
        for i in range(lc):
            if (costs[i][0] < costs[i][1] and al>0) or bl == 0:
                cost2 += costs[i][0]
                al -= 1
            elif bl>0:
                cost2 += costs[i][1]
                bl -= 1
        return min(cost1,cost2)


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        N = len(costs)
        dp = [0]+[float('inf')]*(N//2)
        
        for i in range(1, N+1):
            
            for j in range(N//2, 0, -1):
                dp[j] = min(dp[j]+costs[i-1][1], dp[j-1]+costs[i-1][0])
            dp[0] += costs[i-1][1]
        # print(dp)
        return dp[-1]

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        N = len(costs)//2
        dp = [[0]*(N+1) for _ in range(N+1)]
        for i in range(1, N+1):
            dp[i][0] = dp[i-1][0]+costs[i-1][0]    
        for i in range(1, N+1):
            dp[0][i] = dp[0][i-1]+costs[i-1][1]
            
        for i in range(1, N+1):
            for j in range(1, N+1):
                dp[i][j] = min(dp[i-1][j]+costs[i+j-1][0], dp[i][j-1]+costs[i+j-1][1])
                
        return dp[-1][-1]
            
        


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n = len(costs)
        m = n // 2
        dp = [10 ** 6] * (m + 1)
        dp[m] = 0
        for i in range(n - 1, -1, -1):
            for j in range(m + 1):
                k = i - j
                c = 10 ** 6
                if j < m:
                    c = min(c, costs[i][0] + dp[j + 1])
                if k < m:
                    c = min(c, costs[i][1] + dp[j])
                dp[j] = c
        return dp[0]


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        m = len(costs)
        n = m // 2
        f = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(min(n, i) + 1):
                f[i][j] = math.inf
                if j > 0:
                    f[i][j] = costs[i - 1][0] + f[i - 1][j - 1]
                if i - j > 0:
                    f[i][j] = min(f[i][j], costs[i - 1][1] + f[i - 1][j])
        return f[m][n]

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        
        c = []
        asum = 0
        for i in range(len(costs)):
            a,b = costs[i]
            price = b - a
            asum += a
            c.append(price)

        refunds = sorted(c)
        
        for i in range(len(refunds) // 2):
            asum += refunds[i]
        
        return asum

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        A, B, n = [], [], len(costs) // 2 # person id list
        diff = []
        for i, (a, b) in enumerate(costs):
            diff.append((i, (a - b)))
            if a < b:
                A.append(i)
            else:
                B.append(i)
            
        
        # print(diff)
        # new_A, new_B = [], []
        # diff_num = abs(len(A)-len(B))
        flag = 0
        if len(A) > len(B): # 飞到A的多, 把diff<0且值较小的A放到B, 
            flag = 1
            # 从大到小排序
            diff = sorted(diff, key = lambda x: x[1], reverse=True)
            for i, x in diff:
                if x > 0 or i in B:
                    continue
                B.append(i)
                if len(B) == n:
                    break
            
        elif len(A) < len(B): # 飞到B的多, 把diff>0且值较小的B放到A
            # new_A = A
            flag = 2
            # 从小到大排序
            diff = sorted(diff, key = lambda x: x[1])
            
            for i, x in diff:
                if i in A: continue
                A.append(i)
                if len(A) == n:
                    break
            
        # print(flag, A, B)
        res = 0
        for i in range(2 * n):
            a, b = costs[i]
            if flag == 1:
                res += b if i in B else a
                  
            if flag == 2 or flag == 0:
                res += a if i in A else b                        
      
        return res
            
            
            
            
            
# [1,2], [2,3] ,[3,5],[4,5]
       
# 1 -> A 10
# 2 -> A 30
# 3 -> B 50
# 4 -> B 20

# # A = [10,30]
# # B = [20,200]


# 1 -> A 259


# 2 -> B 54 -54 + 448 = 394
# 3 -> B 667 -667 + 926 = 259 
# 4 -> B 139 - 139 + 184 = 45 -> A
# 5 -> B 118 - 118 + 840 = 772
# 6 -> B 469 - 469 + 577 = 108

# A = [259, 184, 577]
# B = [54， 667， 118]


# min(sum(A) + sum(B)) s.t. len(A) == len(B)





class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        
        diff = [cost[1]-cost[0] for cost in costs]
        heapq.heapify(diff)
        s = 0
        for cost in costs:
            s+=cost[0]
        
        for i in range(len(costs)//2):
            s+=heapq.heappop(diff)
        
        
        return s


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        
        diffs = []
        n = len(costs) / 2
        
        for i, cost in enumerate(costs):
            a, b = cost
            diff = abs(a-b)
            diffs.append((i, diff))
        
        diffs = sorted(diffs, key=lambda x: x[1], reverse=True)
        a_count = 0
        b_count = 0
        cost = 0
        print(diffs)
        for i, diff in diffs:
            city_a = True
            if costs[i][0] > costs[i][1]:
                if b_count < n:
                    b_count += 1
                    cost += costs[i][1]
                else:
                    a_count += 1
                    cost += costs[i][0]
            else:
                if a_count < n:
                    a_count += 1
                    cost += costs[i][0]
                else:
                    b_count += 1
                    cost += costs[i][1]
        return cost


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        
        
        hashmap = collections.defaultdict(int)
        
        for item in costs:
            hashmap[tuple(item)] = abs(item[0]-item[1])
            
        print(hashmap)
        
        
        ll = sorted(hashmap, key = lambda x:-hashmap[x])
        
        print(ll)
        
        n = len(ll)//2
        mincostA = []
        mincostB = []
        
        for i in range(2*n):
            if len(mincostA) < n and len(mincostB) < n:
                if ll[i][0] < ll[i][1]:
                    mincostA.append(ll[i][0]) 
                else:
                    mincostB.append(ll[i][1]) 
                    
            elif len(mincostA) < n:
                mincostA.append(ll[i][0])
                
            elif len(mincostB) < n:
                mincostB.append(ll[i][1]) 
        
        mincost  = 0
        final = mincostA+mincostB
        for i in range(2*n):
            mincost += final[i] 
        
        return mincost
            
            
            
        
        
        
        
        


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key = lambda x:x[0]-x[1])
        print(costs)
        firsthalf = costs[0:len(costs)//2]
        secondhalf = costs[len(costs)//2:]
        return sum(f[0] for f in firsthalf) + sum(s[1] for s in secondhalf)


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n=len(costs)//2
        dp=[ [0 for _ in range(n+1)] for _ in range(n+1) ]
        
        for i in range(1,n+1):
            dp[i][0]=dp[i-1][0] +costs[i-1][0]
        
        for j in range(1,n+1):
            dp[0][j] = dp[0][j-1] + costs[j-1][1]
            
        for a in range(1,n+1):
            for b in range(1,n+1):
                dp[a][b]=min(dp[a-1][b]+costs[a+b-1][0],dp[a][b-1]+costs[a+b-1][1])
        #print (dp)
        return dp[n][n]
        


# sort by difference, where greatest difference is first?
# [[400, 50], [30, 200], [30, 20], [10, 20]]
#   B           A           B         A

# [[840, 118], [259, 770], [448, 54], [926, 667], [577, 469], [184, 139]]
#       B           A           B          B          A            A 

# [[631, 42], [343, 819], [457, 60], [650, 359], [451, 713], [536, 709], [855, 779], [515, 563]]
#      B          A           B          B           A           A           B           A

# seemingly works for the given cases

# why??

# positives outweight the negatives 
# we will be positive for at least the first n iterations (worst case we pick one city for the first n iterations)

# since we sorted by greatest difference first we will be maximizing our profits by taking 
# the optimal choice when the difference is greatest

# we have costs[i] and costs[j] where i <= n and n < j < 2n and difference[i] > difference[j]
# if we make the optimal choice we will be up difference[i] - difference[j]

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        sortedCosts = sorted(costs, key = lambda x: abs(x[0] - x[1]), reverse=True)
        numA = 0
        numB = 0
        res = 0
        
        for cost in sortedCosts:
            if numB >= len(sortedCosts) / 2:
                res += cost[0]
            
            elif numA >= len(sortedCosts) / 2:
                res += cost[1]
            
            else:
                if cost[0] < cost[1]:
                    res += cost[0]
                    numA += 1
                else:
                    res += cost[1]
                    numB += 1
        
        return res