Two City Scheduling

Explanation & Solution

Description

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCost_i, bCost_i], the cost of flying the i-th person to city A is aCost_i and the cost of flying the i-th person to city B is bCost_i.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

Input: costs = [[10,20],[30,200],[400,50],[30,20]]

Output: 110

Explanation: Person 0 goes to city A (cost 10), person 1 goes to city A (cost 30), person 2 goes to city B (cost 50), person 3 goes to city B (cost 20). Total = 10 + 30 + 50 + 20 = 110.

Constraints

2 * n == costs.length
2 <= costs.length <= 100
costs.length is even
1 <= aCost_i, bCost_i <= 1000

Approach

Greedy Techniques pattern

1. Compute the Cost Difference

For each person, consider the difference aCost - bCost
A negative difference means flying to city A is relatively cheaper
A positive difference means flying to city B is relatively cheaper

2. Sort by the Difference

Sort the entire costs array by (aCost - bCost) in ascending order
After sorting, people who benefit most from going to city A appear first, and people who benefit most from going to city B appear last

3. Split into Two Halves

Send the first n people (smallest differences) to city A — these are the people for whom city A is the best relative deal
Send the last n people (largest differences) to city B — these are the people for whom city B is the best relative deal

4. Sum the Costs

For each person in the first half, add their aCost to the total
For each person in the second half, add their bCost to the total
Return the accumulated total as the minimum cost

Key Insight

The greedy strategy works because sorting by the relative savings (aCost - bCost) optimally partitions the people into two equal groups
By always assigning the person with the greatest relative advantage to their preferred city, we guarantee the global minimum cost

Time

O(n log n) due to sorting

Space

O(1) extra space (in-place sort)

Solution Code

Queue Reconstruction by Height

Minimum Number of Refueling Stops