## Similar Problems

Similar Problems not available

# Two City Scheduling - Leetcode Solution

## Companies:

LeetCode: Two City Scheduling Leetcode Solution

Difficulty: Medium

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.

## Two City Scheduling Solution Code

`1`