LeetCode 1029 - Two City Scheduling

LeetCode Problem 1029

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

In this problem, we are given an array called costs, where each element represents the travel cost for one person to two different cities. Specifically, costs[i] = [aCosti, bCosti] means:

• aCosti is the cost of flying person i to city A
• bCosti is the cost of flying person i to city B

There are exactly 2n people, and we must send exactly n people to city A and exactly n people to city B.

The goal is to minimize the total travel cost while satisfying the equal distribution requirement.

For example, if a person costs much less to send to city A than city B, we would prefer sending them to city A. However, we cannot simply choose the cheaper city for everyone because we must keep the number of people balanced between the two cities.

The constraints are relatively small:

• 2 <= costs.length <= 100
• costs.length is always even
• Costs are positive integers

Although the input size is not huge, the problem is fundamentally combinatorial because every person has two choices. A naive solution could try every possible assignment, but the number of combinations grows exponentially.

Several edge cases are important to consider:

• Multiple people may have identical costs for both cities.
• Some people may strongly favor one city over the other.
• The cheapest local decision for one person may prevent a globally optimal balanced assignment.
• Since exactly half the people must go to each city, we must carefully track counts.

The problem guarantees valid input, so we do not need to handle malformed arrays or odd lengths.

Approaches

Brute Force Approach

A brute force solution would try every possible assignment of people to cities while ensuring exactly half go to each city.

For every person, we have two choices:

• Send them to city A
• Send them to city B

This creates 2^(2n) possible assignments in total. We would then filter the assignments that send exactly n people to each city and compute the minimum total cost.

This approach is guaranteed to find the correct answer because it exhaustively checks every valid arrangement. However, it becomes computationally expensive very quickly because the number of combinations grows exponentially.

Even with only 100 people, brute force is completely impractical.

Key Insight for the Optimal Solution

The important observation is that what matters is not the absolute cost of each city, but the difference between sending a person to city A versus city B.

For each person, compute:

$$aCost - bCost$$

This value tells us how much cheaper or more expensive city A is compared to city B.

• A large negative value means city A is much cheaper.
• A large positive value means city B is much cheaper.

If we sort people by this difference:

• People who strongly prefer city A appear first.
• People who strongly prefer city B appear last.

Then we can:

• Send the first n people to city A
• Send the remaining n people to city B

This greedy strategy works because sorting by cost difference ensures that the people with the greatest advantage for city A are assigned there first.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(2n))	O(2n)	Tries every possible assignment
Optimal Greedy + Sorting	O(n log n)	O(1) or O(n) depending on sort implementation	Uses cost differences to make optimal assignments

Algorithm Walkthrough

1. For each person, compute the difference between flying them to city A and city B.

The difference is:

$$aCost - bCost$$

A negative difference means city A is cheaper. A positive difference means city B is cheaper. 2. Sort the people based on this difference.

After sorting:

• People at the beginning strongly prefer city A.
• People at the end strongly prefer city B.

3. Send the first half of the sorted people to city A.

Since these people have the smallest differences, assigning them to city A saves the most money. 4. Send the second half of the sorted people to city B.

These people either prefer city B or lose the least money by going there. 5. Sum all selected travel costs and return the total.

Why it works

The greedy property comes from comparing relative savings.

Suppose two people are assigned incorrectly:

• One person who strongly prefers city A is sent to city B.
• Another person who strongly prefers city B is sent to city A.

Swapping their assignments would always reduce the total cost.

Sorting by the difference aCost - bCost guarantees that the people with the largest benefit for city A are chosen first. Therefore, no better reassignment exists after sorting.

Python Solution

from typing import List

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda person: person[0] - person[1])

        n = len(costs) // 2
        total_cost = 0

        for i in range(n):
            total_cost += costs[i][0]

        for i in range(n, 2 * n):
            total_cost += costs[i][1]

        return total_cost

The implementation begins by sorting the array using the difference between the cost to city A and city B.

person[0] - person[1]

This value determines how strongly a person prefers city A over city B.

After sorting, the first half of the array contains the people who are best suited for city A. The second half contains the people best suited for city B.

We compute n as half the number of people. Then:

• The first loop adds city A costs for the first n people.
• The second loop adds city B costs for the remaining n people.

Finally, the total minimum cost is returned.

Go Solution

import "sort"

func twoCitySchedCost(costs [][]int) int {
	sort.Slice(costs, func(i, j int) bool {
		return (costs[i][0] - costs[i][1]) < (costs[j][0] - costs[j][1])
	})

	n := len(costs) / 2
	totalCost := 0

	for i := 0; i < n; i++ {
		totalCost += costs[i][0]
	}

	for i := n; i < 2*n; i++ {
		totalCost += costs[i][1]
	}

	return totalCost
}

The Go implementation follows the same logic as the Python solution.

The primary difference is the use of sort.Slice to sort the two-dimensional slice with a custom comparator function.

Go slices are reference-like structures, so sorting modifies the original slice in place.

Integer overflow is not a concern because the maximum possible total cost is well within Go's integer range.

Worked Examples

Example 1

Input:

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

Step 1: Compute Differences

Person	A Cost	B Cost	Difference (A - B)
0	10	20	-10
1	30	200	-170
2	400	50	350
3	30	20	10

Step 2: Sort by Difference

Person	Difference
[30,200]	-170
[10,20]	-10
[30,20]	10
[400,50]	350

Step 3: Assign Cities

There are 4 people, so n = 2.

Person	Assigned City	Cost
[30,200]	A	30
[10,20]	A	10
[30,20]	B	20
[400,50]	B	50

Final Cost

30 + 10 + 20 + 50 = 110

Example 2

Input:

costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]

Compute Differences

Person	Difference
[259,770]	-511
[448,54]	394
[926,667]	259
[184,139]	45
[840,118]	722
[577,469]	108

Sorted Order

Person	Difference
[259,770]	-511
[184,139]	45
[577,469]	108
[926,667]	259
[448,54]	394
[840,118]	722

Assignments

First 3 go to city A:

259 + 184 + 577 = 1020

Last 3 go to city B:

667 + 54 + 118 = 839

Final Cost

1020 + 839 = 1859

Example 3

Input:

costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]

Compute Differences

Person	Difference
[515,563]	-48
[451,713]	-262
[537,709]	-172
[343,819]	-476
[855,779]	76
[457,60]	397
[650,359]	291
[631,42]	589

Sorted Order

Person	Difference
[343,819]	-476
[451,713]	-262
[537,709]	-172
[515,563]	-48
[855,779]	76
[650,359]	291
[457,60]	397
[631,42]	589

Assignments

First 4 to city A:

343 + 451 + 537 + 515 = 1846

Last 4 to city B:

779 + 359 + 60 + 42 = 1240

Final Cost

1846 + 1240 = 3086

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(n)	Depends on sorting implementation

The algorithm spends most of its time sorting the array by cost difference. After sorting, the final summation pass is linear.

Python's sorting implementation may use additional memory internally, while Go's sort implementation performs in-place sorting with small auxiliary overhead.

Test Cases

from typing import List

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda person: person[0] - person[1])

        n = len(costs) // 2
        total_cost = 0

        for i in range(n):
            total_cost += costs[i][0]

        for i in range(n, 2 * n):
            total_cost += costs[i][1]

        return total_cost

solution = Solution()

assert solution.twoCitySchedCost(
    [[10,20],[30,200],[400,50],[30,20]]
) == 110  # basic example

assert solution.twoCitySchedCost(
    [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
) == 1859  # larger mixed preferences

assert solution.twoCitySchedCost(
    [[515,563],[451,713],[537,709],[343,819],
     [855,779],[457,60],[650,359],[631,42]]
) == 3086  # larger input

assert solution.twoCitySchedCost(
    [[10,10],[20,20]]
) == 30  # equal costs for both cities

assert solution.twoCitySchedCost(
    [[1,1000],[2,999],[999,3],[1000,4]]
) == 10  # extreme preference split

assert solution.twoCitySchedCost(
    [[100,200],[101,201]]
) == 301  # minimum valid size

assert solution.twoCitySchedCost(
    [[50,50],[50,50],[50,50],[50,50]]
) == 200  # all costs identical

assert solution.twoCitySchedCost(
    [[5,100],[6,101],[102,1],[103,2]]
) == 14  # strong greedy separation

Test Case Summary

Test	Why
Basic example	Verifies standard functionality
Larger mixed preferences	Tests sorting correctness
Eight-person example	Tests scalability and ordering
Equal costs	Ensures ties are handled correctly
Extreme preference split	Verifies greedy assignment
Minimum valid size	Tests smallest allowed input
Identical costs	Ensures balanced assignment still works
Strong separation	Confirms correct city partitioning

Edge Cases

One important edge case occurs when multiple people have identical costs for both cities. In this situation, the difference aCost - bCost becomes zero for many entries. A buggy implementation might incorrectly assume strict ordering is necessary. The sorting-based solution handles this naturally because any assignment among equal-difference people produces the same total contribution.

Another important edge case is when every person strongly prefers the same city. For example, everyone may be much cheaper to send to city A. A naive greedy solution that always picks the cheapest city per person would fail because it would violate the requirement that exactly half the people go to each city. The implemented algorithm correctly balances assignments by sorting and splitting evenly.

The minimum input size is also important. When only two people exist, exactly one must go to each city. Off-by-one errors frequently appear in partitioning logic for small inputs. The implementation correctly computes:

n = len(costs) // 2

and uses precise loop boundaries to ensure each city receives exactly one person.

A final edge case involves large cost differences. Some people may have extremely large penalties for going to the wrong city. Sorting by difference guarantees that the algorithm prioritizes those high-impact decisions first, preventing costly misassignments.