'''
keys: greedy, sort at first O(nlogn), then solution O(n)
Solutions:
Similar:
T:
S:
'''
from typing import List


class Solution:
    # T: O(nlogn); S: O(1)
    # sort by priceA - priceB, send first N to A
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key = lambda x: x[0] - x[1])
        
        res = 0
        n = len(costs)//2 # always even number of people
        for i in range(n): 
            res += costs[i][0] + costs[i+n][1]
        return res


    # https://leetcode.com/problems/two-city-scheduling/discuss/667786/Java-or-C%2B%2B-or-Python3-or-With-detailed-explanation
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        refund = []
        N = len(costs) // 2
        minCost = 0
        for A, B in costs: # refund is the amount when you send people to B
            refund.append(B - A) # track refund for each one
            minCost += A # send all people to A first
        refund.sort() # negatives first
        for i in range(N): # send those with max refund to B
            minCost += refund[i] # abstract the refunds
        return minCost