Two City Scheduling - Leetcode Solution

The Two City Scheduling problem on LeetCode is a problem in which we are given a list of costs, which represent the cost of sending a person to one of two different cities. We have to find the minimum cost of sending all the people to two different cities such that an equal number of people are sent to each city.

To solve this problem, we can use the following steps:

Step 1: Sort the list of costs in increasing order.

Step 2: Divide the list of costs into two equal parts, such that the first half represents the cost of sending people to the first city and the second half represents the cost of sending people to the second city.

Step 3: Calculate the total cost of sending all the people to the first city and the total cost of sending all the people to the second city.

Step 4: Return the minimum of the two total costs.

Here is the Python code for the Two City Scheduling problem using the above steps:

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        # Sort the list of costs in increasing order
        costs.sort(key=lambda x: x[1] - x[0])
        
        # Divide the costs into two equal parts
        n = len(costs) // 2
        
        # Calculate the total cost of sending all the people to the first city
        total_cost_a = sum(x[0] for x in costs[:n])
        
        # Calculate the total cost of sending all the people to the second city
        total_cost_b = sum(x[1] for x in costs[n:])
        
        # Return the minimum of the two total costs
        return total_cost_a + total_cost_b

The time complexity of this solution is O(nlogn), where n is the length of the list of costs, due to the sorting of the list. The space complexity is O(1) since we are using constant extra space.

1