{x}
blog image

Two City Scheduling

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

 

Example 1:

Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
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 3:

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

 

Constraints:

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

Solution Explanation for 1029. Two City Scheduling

This problem involves finding the minimum cost to send n people to city A and n people to city B, given a cost matrix where costs[i] = [aCost_i, bCost_i] represents the cost of sending person i to city A and city B respectively.

The optimal solution leverages a greedy approach. The core idea is to sort the costs based on the difference between the cost of sending a person to city A and the cost of sending them to city B (aCost_i - bCost_i).

Algorithm:

  1. Sort: Sort the costs array based on the difference aCost_i - bCost_i. People with a smaller difference (meaning it's cheaper to send them to city A) will come earlier in the sorted array.

  2. Assign: Assign the first n people to city A and the remaining n people to city B. This ensures that we send the people who are significantly cheaper to send to city A to city A first.

  3. Calculate Total Cost: Sum the costs of sending the assigned people to their respective cities. This sum represents the minimum total cost.

Time Complexity Analysis:

  • Sorting the array takes O(N log N) time, where N is the number of people (which is equal to 2n).
  • The loop to calculate the total cost takes O(N) time.

Therefore, the overall time complexity is dominated by the sorting step, resulting in O(N log N).

Space Complexity Analysis:

The space complexity depends on the sorting algorithm used. In-place sorting algorithms like merge sort or quicksort have a space complexity of O(log N) (due to the recursive calls in the worst-case for quicksort). If a non-in-place sorting algorithm is used like merge sort, it will have O(N) auxiliary space. Thus space complexity can vary between O(log N) and O(N) based on the sorting algorithm used.

Code Explanation (Python):

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda x: x[0] - x[1])  #Sort by difference (aCost - bCost)
        n = len(costs) // 2  #Number of people to send to each city
        total_cost = 0
        for i in range(n):
            total_cost += costs[i][0] + costs[i + n][1] #Sum costs (first n to A, next n to B)
        return total_cost

The Python code directly implements the algorithm described above. The lambda function provides a concise way to specify the sorting key. The code efficiently calculates the total cost in a single loop. Other languages follow a similar structure, differing only in syntax and libraries used for sorting.