How do you solve Two City Scheduling on LeetCode?

Two City Scheduling (LeetCode #1029) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(1) space complexity. Key insight: Sorting based on cost differences helps prioritize cheaper options.

What is the time complexity of Two City Scheduling?

The optimal solution for Two City Scheduling runs in O(n log n) time and uses O(1) space. The sorting step dominates the time complexity, making it O(n log n). The subsequent summation is O(n), which is efficient.

What is the brute force solution for Two City Scheduling?

The brute force approach for Two City Scheduling is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we explore every possible way to assign people to cities A and B. This means we would try all combinations of sending n people to city A and the remaining to city B, calculating the total cost for each combination. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Two City Scheduling?

Two City Scheduling uses the following concepts: Array, Greedy, Sorting. The recommended patterns to study are: Greedy, Sorting.

What are the interview tips for Two City Scheduling?

Always consider edge cases, such as when costs are equal. Explain your thought process clearly while coding. Practice similar problems to get comfortable with greedy algorithms.

What are common mistakes when solving Two City Scheduling?

Failing to sort based on the cost differences, leading to suboptimal solutions. Not ensuring exactly n people are sent to each city.

#1029

Two City Scheduling

Medium

ArrayGreedySortingGreedySorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(1)

💡

Intuition

Time O(n log n)Space O(1)

In the optimal approach, we leverage sorting based on the difference between costs for cities A and B. This helps us prioritize which people should be sent to which city based on the cost difference, ensuring we minimize the total cost while maintaining the balance of n people in each city.

⚙️

Algorithm

4 steps

1Step 1: Calculate the difference between the costs for each person to go to city A and city B.
2Step 2: Sort the array based on these differences.
3Step 3: Select the first n people to go to city A and the remaining n people to go to city B.
4Step 4: Sum the costs for the selected people to get the minimum total cost.

solution.py5 lines

1# Full working Python code
2def twoCitySchedCost(costs):
3    costs.sort(key=lambda x: x[0] - x[1])
4    n = len(costs) // 2
5    return sum(costs[i][0] for i in range(n)) + sum(costs[i][1] for i in range(n, 2 * n))

ℹ

Complexity note: The sorting step dominates the time complexity, making it O(n log n). The subsequent summation is O(n), which is efficient.

1Sorting based on cost differences helps prioritize cheaper options.
2Balancing the number of people in each city is crucial for minimizing costs.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.