NeetCode #798LC-1029MediumGreedy
← Back to All Problems#798 · #1029 · Two City Scheduling(两地调度)
📌 Problem Statement & Constraints
A company must send
2n people to two cities, n to each. costs[i] = [costA, costB] is the cost of sending person i to city A or city B. Return the minimum total cost. Constraints: 2 <= costs.length <= 100 and costs.length is even, 1 <= costs[i][0], costs[i][1] <= 1000.💡 Core Algorithmic Approaches
- Assigning a person to B instead of A costs
costB - costAextra relative to sending everyone to A. - To minimise, we must choose exactly
npeople to send to B, and we want the smallest extra costs. - Sort by the difference
costA - costB; the firstnhave the largest savings from going to A. - Send the first half to A and the second half to B.
💻 Benchmark Python3 Implementation
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
costs.sort(key=lambda c: c[0] - c[1])
n = len(costs) // 2
total = sum(c[0] for c in costs[:n]) # cheaper in A
total += sum(c[1] for c in costs[n:]) # cheaper in B
return total⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(1) beyond the sort.
⚠️ Interview Pitfalls & Follow-ups
- Sorting by
costAalone: the decision depends on the difference between the two cities. - Sending the first half to B: the sorted order puts the most A-favourable people first.
- Forgetting that exactly
ngo to each city: the split must be even. - Using a greedy nearest-city assignment: it can overload one city, so the difference sort is required.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.