LeetCode 1029: Two City Scheduling

Brute force

Try flying each person to city A and city B and take the minimum cost.

Time: $\mathcal{O}(2^n)$ , space: $\mathcal{O}(n)$ .

class Solution:
    def explore(self, i, costs, first_count, second_count, curr_cost):
        if i == len(costs):
            if first_count == second_count:
                return curr_cost
            return float("inf")
        
        return min(
            self.explore(i+1, costs, first_count+1, second_count, curr_cost+costs[i][0]),
            self.explore(i+1, costs, first_count, second_count+1, curr_cost+costs[i][1])
        )

    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        return self.explore(0, costs, 0, 0, 0)

Greedy

For a cost pair $(c_A, c_B)$ , when we decide to fly a person to city A, we are also deciding to not fly that person to city B. We have to optimize both of these sub-decisions: minimize $c_A$ and maximize $c_B$ . Minimizing the cost differential $(c_A - c_B)$ achieves both.

For example, between two cost pairs: $(10, 20)$ and $(30, 200)$ , although $10 < 30$ we would prefer flying a person to city A with cost $30$ because that would eliminate the super expensive choice of $200$ . So, total cost would be $20+30 = 50$ instead of $10+200 = 210$ .

Time: $\mathcal{O}(n \cdot \lg{n})$ , space: $\mathcal{O}(\texttt{sorting-space})$ .

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda pair: pair[0] - pair[1])
        n = len(costs) // 2
        return sum(costs[i][0] for i in range(n)) + sum(costs[i][1] for i in range(n, len(costs)))

unreasonably effective