Two City Scheduling

Medium Subject: Greedy

Time Complexity

O(N log N)

Space Complexity

O(1)

Problem Description

Problem Statement

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

Optimal Solution

Python

Approach: Greedy Sort by Cost Difference

Sort the costs array based on the difference between flying to city A vs city B (a_cost - b_cost). The first half of the sorted list represents people for whom it is significantly cheaper to fly to A. The second half should fly to B.

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda x: x[0] - x[1])
        n = len(costs) // 2
        total = 0

        for i in range(n):
            total += costs[i][0]  # Fly to A
        for i in range(n, 2 * n):
            total += costs[i][1]  # Fly to B

        return total