Problem Description

You have 2n people that need to be interviewed, and the company wants to conduct interviews in two different cities (city A and city B). Each person must be flown to exactly one city for their interview.

For each person i, you're given the costs to fly them to each city:

• aCost[i] - the cost to fly person i to city A
• bCost[i] - the cost to fly person i to city B

These costs are provided in an array costs where costs[i] = [aCost[i], bCost[i]].

The constraint is that you must send exactly n people to city A and exactly n people to city B (splitting the 2n people evenly between the two cities).

Your task is to find the minimum total cost to fly all 2n people to their assigned cities while maintaining this even split.

For example, if you have 4 people (2n = 4, so n = 2) with costs:

• Person 0: [10, 20] (costs $10 to city A,$20 to city B)
• Person 1: [30, 200] (costs $30 to city A,$200 to city B)
• Person 2: [400, 50] (costs $400 to city A,$50 to city B)
• Person 3: [30, 20] (costs $30 to city A,$20 to city B)

You need to choose which 2 people go to city A and which 2 go to city B to minimize the total cost.

Intuition

The key insight is to think about the relative cost difference between sending each person to city A versus city B. For each person, we can calculate how much we "save" or "lose" by choosing city A over city B.

Consider this: if we send person i to city A instead of city B, the relative cost difference is costs[i][0] - costs[i][1].

• If this value is negative, it means city A is cheaper for this person
• If this value is positive, it means city B is cheaper for this person

For example, if person i costs [10, 30], the difference is 10 - 30 = -20, meaning we save $20 by sending them to city A instead of city B.

Now, since we must send exactly n people to each city, we want to:

1. Send the n people who have the most negative (or least positive) difference to city A
2. Send the remaining n people to city B

Why does this work? By sorting people based on costs[i][0] - costs[i][1], we're arranging them from those who benefit most from going to city A (large negative differences) to those who benefit least (or actually cost more to go to city A, with positive differences).

After sorting by this difference:

• The first n people in the sorted list are the ones where city A is relatively cheapest (or least expensive compared to B)
• The last n people are the ones where city B is relatively cheapest

This greedy approach ensures we're making the most cost-effective assignment while respecting the constraint of sending exactly n people to each city. We're essentially maximizing our "savings" by sending each person to their relatively cheaper destination whenever possible, within the constraints.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a greedy approach using sorting based on cost differences:

1. Sort by Cost Difference: First, we sort the entire costs array based on the difference between city A cost and city B cost for each person:

   costs.sort(key=lambda x: x[0] - x[1])

   This lambda function x[0] - x[1] calculates the relative cost of sending each person to city A versus city B. After sorting, people who should preferably go to city A (negative or small differences) appear first.

2. Calculate n: We determine how many people should go to each city:

   n = len(costs) >> 1

   The bit shift operation >> 1 is equivalent to dividing by 2, giving us n (half of 2n people).

3. Assign Cities and Calculate Total Cost: After sorting, we use a simple strategy:

   • Send the first n people to city A (these have the smallest A - B differences)
   • Send the last n people to city B

   The total cost calculation is done in one line:

   return sum(costs[i][0] + costs[i + n][1] for i in range(n))

   Breaking this down:

   • costs[i][0] for i in range [0, n) → cost of sending first n people to city A
   • costs[i + n][1] for i in range [0, n) → cost of sending people at indices [n, 2n) to city B

Time Complexity: O(n log n) due to sorting, where n is the total number of people (note: the problem uses 2n people, so technically O(2n log 2n) which simplifies to O(n log n)).

Space Complexity: O(1) if we don't count the space used by the sorting algorithm (which is typically O(log n) for the recursion stack in languages like Python).

The elegance of this solution lies in recognizing that sorting by the cost difference automatically groups people by their optimal city assignment while respecting the constraint of equal distribution.

Example Walkthrough

Let's walk through a small example with 4 people (2n = 4, so n = 2):

Given costs:

• Person 0: [10, 20] (costs $10 to city A,$20 to city B)
• Person 1: [30, 200] (costs $30 to city A,$200 to city B)
• Person 2: [400, 50] (costs $400 to city A,$50 to city B)
• Person 3: [30, 20] (costs $30 to city A,$20 to city B)

Step 1: Calculate cost differences (A - B) for each person

• Person 0: 10 - 20 = -10 (saving $10 by choosing city A)
• Person 1: 30 - 200 = -170 (saving $170 by choosing city A)
• Person 2: 400 - 50 = 350 (losing $350 by choosing city A)
• Person 3: 30 - 20 = 10 (losing $10 by choosing city A)

Step 2: Sort people by their cost differences (ascending) After sorting by difference:

1. Person 1: [30, 200] with difference = -170
2. Person 0: [10, 20] with difference = -10
3. Person 3: [30, 20] with difference = 10
4. Person 2: [400, 50] with difference = 350

Step 3: Assign cities based on sorted order

• First n=2 people go to city A:
  • Person 1 → city A: cost = $30
  • Person 0 → city A: cost = $10
• Last n=2 people go to city B:
  • Person 3 → city B: cost = $20
  • Person 2 → city B: cost = $50

Step 4: Calculate total cost Total = 30 + 10 + 20 + 50 = $110

This assignment makes sense because we sent the people with the most negative differences (who benefit most from city A) to city A, and the people with positive differences (who prefer city B) to city B, achieving the minimum total cost while maintaining the n/n split.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the total number of people (length of the costs array).

• The sorting operation costs.sort(key=lambda x: x[0] - x[1]) dominates the time complexity, which takes O(n log n) time.
• The subsequent sum operation with list comprehension iterates through n/2 elements, taking O(n/2) = O(n) time.
• Overall: O(n log n) + O(n) = O(n log n)

Space Complexity: O(1) or O(n) depending on the sorting algorithm implementation.

• The sort is performed in-place on the input array, so no additional space is needed for storing a separate sorted array.
• The list comprehension in the sum creates a generator expression which uses O(1) space.
• However, Python's Timsort (used in .sort()) may use up to O(n) auxiliary space in the worst case for its merge operations.
• If we consider only the extra space explicitly allocated by the algorithm (excluding sort's internal space), it's O(1).
• If we include the sorting algorithm's space requirements, it's O(n) in the worst case.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Sorting Logic

A common mistake is incorrectly implementing the sorting comparator. Some developers might sort by x[1] - x[0] instead of x[0] - x[1], which would reverse the optimal assignment.

Wrong approach:

costs.sort(key=lambda x: x[1] - x[0])  # This sorts in the wrong order!

Why it matters: The difference x[0] - x[1] represents how much MORE it costs to send someone to city A compared to city B. A negative value means city A is cheaper for that person. By sorting in ascending order of this difference, we prioritize people who save the most money by going to city A.

2. Off-by-One Errors in Index Calculation

When calculating the sum, developers might make indexing errors:

Common mistakes:

# Mistake 1: Using wrong indices for city B
return sum(costs[i][0] + costs[n + i][1] for i in range(n))  # Should be costs[i + n][1]

# Mistake 2: Incorrect range
return sum(costs[i][0] for i in range(n)) + sum(costs[i][1] for i in range(n, len(costs)))
# While this works, it's less elegant and more prone to errors

3. Not Handling Edge Cases

Although the problem guarantees 2n people, defensive programming suggests checking:

Improved solution with validation:

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        if not costs or len(costs) % 2 != 0:
            return 0  # or raise an exception
      
        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))

4. Overthinking with Dynamic Programming

Some developers might immediately reach for DP when they see an optimization problem with constraints. While DP can solve this problem, it's unnecessarily complex:

Overcomplicated DP approach (avoid this):

# This works but is overkill - O(n²) space and time
dp = {}
def solve(i, a_count):
    if i == len(costs):
        return 0 if a_count == n else float('inf')
    if (i, a_count) in dp:
        return dp[(i, a_count)]
    # ... more complex DP logic

The greedy approach is both simpler and more efficient for this specific problem structure.