⚡Flashcard Drill➔
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

  1. Assigning a person to B instead of A costs costB - costA extra relative to sending everyone to A.
  2. To minimise, we must choose exactly n people to send to B, and we want the smallest extra costs.
  3. Sort by the difference costA - costB; the first n have the largest savings from going to A.
  4. 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 costA alone: 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 n go 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems