#1029

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Two City Scheduling

Two City Scheduling requires selecting optimal city assignments for 2n people to minimize total travel costs efficiently.

array greedy sorting

Problem Statement

A company needs to fly 2n people to two different cities for interviews. Each person has individual costs for city A and city B provided in a 2D array costs where costs[i] = [aCosti, bCosti]. The goal is to assign exactly n people to each city while minimizing total travel costs.

Given the array costs, return the minimum total cost required to send each person to a city under the n-per-city constraint. For example, for costs = [[10,20],[30,200],[400,50],[30,20]], the optimal assignment sends the first two people to city A and the last two to city B for a total cost of 110.

Examples

Example 1

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

Output: 110

The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Example 2

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

Output: 1859

Example details omitted.

Example 3

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

Output: 3086

Example details omitted.

Constraints

2 * n == costs.length
2 <= costs.length <= 100
costs.length is even.
1 <= aCosti, bCosti <= 1000

Solution Approach

Compute Cost Differences

For each person, calculate the difference between the cost of going to city A and city B. This highlights which city is cheaper for that person and sets up the greedy assignment decision.

Sort by Savings Potential

Sort the people based on the computed cost differences. Those with the largest negative difference should prefer city A, and the largest positive difference prefer city B. Sorting ensures the greedy choice maximizes cost savings incrementally.

Assign Exactly n People per City

After sorting, assign the first n people to city A and the remaining n people to city B. This maintains the invariant of having exactly n people in each city while applying the greedy cost-minimizing decision.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is dominated by the sorting step, O(n log n), and space complexity is O(n) for storing differences and sorting indexes.

What Interviewers Usually Probe

Candidate considers individual cost differences and recognizes sorting as a key step.
Candidate validates that exactly n people are assigned per city to avoid constraint violations.
Candidate can explain why the greedy assignment leads to a globally minimal cost rather than just a local choice.

Common Pitfalls or Variants

Common pitfalls

Failing to maintain exactly n people per city after sorting, which violates problem constraints.
Sorting by absolute cost instead of the cost difference, leading to suboptimal total cost.
Overlooking edge cases where multiple people have identical cost differences, potentially affecting assignment order.

Follow-up variants

Assigning people to three cities instead of two with the same minimal cost goal.
Considering additional constraints like flight availability or maximum individual cost per person.
Handling large input sizes where sorting efficiency becomes critical and alternative data structures may help.

FAQ

What is the main pattern behind Two City Scheduling?

It is a greedy choice plus invariant validation problem where sorting by cost difference allows optimal assignment.

How do you ensure exactly n people go to each city?

After sorting by cost difference, assign the first n people to city A and the rest to city B, preserving the n-per-city invariant.

Can this approach fail for large n?

The approach is efficient; sorting dominates time complexity as O(n log n), which scales well for n up to 50 (2n = 100).

Why not simply assign each person to their cheaper city?

Greedy assignment without considering the n-per-city constraint may overload one city and lead to higher total cost.

Does GhostInterview provide the final minimal cost?

Yes, it calculates the cost differences, applies the greedy assignment, and returns the exact minimum total travel cost.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda x: x[0] - x[1])
        n = len(costs) >> 1
        return sum(costs[i][0] + costs[i + n][1] for i in range(n))

Continue Practicing

#1005 maximize sum of array after k negations #1054 distant barcodes #976 largest perimeter triangle