Two City Scheduling

Medium

Google

2 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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

Could you write an algorithm to efficiently solve this problem?

Two City Scheduling

Medium

Google

2 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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

Could you write an algorithm to efficiently solve this problem?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the `costs` array?
Are the costs in the `costs` array guaranteed to be non-negative?
Is it guaranteed that `costs.length` will always be an even number?
If there are multiple possible minimum costs, can I return any one?
If a city is already at its capacity (n), how do I handle assigning additional people to it?

Brute Force Solution

Approach

The brute force approach to the Two City Scheduling problem involves checking every possible assignment of people to cities. We explore every combination of sending people to City A or City B. Since we want the absolute best (minimum) cost, we need to check everything.

Here's how the algorithm would work step-by-step:

Consider each person and decide whether to send them to City A or City B.
For each person, track the cost of sending them to City A and the cost of sending them to City B.
Try all possible combinations of sending people to the cities, making sure that exactly half of the people go to City A and the other half go to City B.
For each possible combination, calculate the total cost by adding up the individual costs of sending each person to their assigned city.
After checking every possible valid combination, find the combination with the lowest total cost. That's the optimal solution.

Code Implementation

def two_city_scheduling_brute_force(costs):
    number_of_people = len(costs)
    half_people = number_of_people // 2
    minimum_cost = float('inf')

    def calculate_cost(assignment):
        city_a_count = 0
        total_cost_of_assignment = 0

        for person_index in range(number_of_people):
            if assignment[person_index] == 0:
                city_a_count += 1
                total_cost_of_assignment += costs[person_index][0]
            else:
                total_cost_of_assignment += costs[person_index][1]

        if city_a_count == half_people:
            return total_cost_of_assignment
        else:
            return float('inf')

    def generate_assignments(index, current_assignment):
        nonlocal minimum_cost

        # Base case: all people have been assigned
        if index == number_of_people:
            cost_for_assignment = calculate_cost(current_assignment)
            minimum_cost = min(minimum_cost, cost_for_assignment)
            return

        # Try assigning the current person to City A
        generate_assignments(index + 1, current_assignment + [0])

        # Try assigning the current person to City B
        generate_assignments(index + 1, current_assignment + [1])

    # Initiate recursive search to find minimum cost
    # Starting with an empty assignment (no cities assigned)
    generate_assignments(0, [])

    return minimum_cost

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible combinations of assigning n people to two cities, with the constraint that n/2 people go to each city. Since each person can be sent to either city A or city B, we have 2 choices for each person. Thus we're considering all subsets of size n/2 from a set of size n. Calculating combinations of n items taken n/2 at a time, (n choose n/2), is approximately equivalent to 2^n for larger values of n. Therefore, the time complexity is O(2^n).

Space Complexity

O(1) – The brute force approach described primarily involves iterating and calculating costs. It does not explicitly mention creating auxiliary data structures like lists, hash maps, or large arrays to store intermediate results or combinations. It checks different combinations by recalculating costs, rather than storing them. The space usage is therefore limited to a few variables for loop indices and cost calculations, which remain constant irrespective of N, the number of people. Thus, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem asks us to minimize the total cost of sending people to two different cities. The key insight is to first sort the people based on how much more expensive it is to send them to one city versus the other, then assign the first half to one city, and the second half to the other.

Here's how the algorithm would work step-by-step:

For each person, figure out the difference in cost between sending them to City A and sending them to City B. This difference tells us how much 'better' or 'worse' it is to send someone to City A.
Sort all the people based on these cost differences, from the most 'beneficial' to send to City A to the least 'beneficial'. This gives us a prioritized order.
Send the first half of the sorted people to City A. These are the people for whom going to City A saves the most money or costs the least extra.
Send the remaining half of the people to City B. These are the people for whom going to City B saves the most money or costs the least extra.
Calculate the total cost by adding up the costs of sending each person to their assigned city.

Code Implementation

def two_city_scheduling(costs):
    # Sort by the difference in cost to optimize assignment
    costs.sort(key=lambda cost: cost[0] - cost[1])

    number_of_people = len(costs)
    city_a_count = number_of_people // 2
    total_cost = 0

    # Assign the first half to city A
    for i in range(city_a_count):
        total_cost += costs[i][0]

    # Assign the second half to city B
    for i in range(city_a_count, number_of_people):
        total_cost += costs[i][1]

    return total_cost

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this solution is the sorting step. We calculate the cost difference for each of the n people, which takes O(n) time. The sorting algorithm, typically implemented using an efficient algorithm like merge sort or quicksort, has a time complexity of O(n log n). The remaining operations (assigning people to cities and calculating the total cost) each take O(n) time. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The dominant space complexity comes from the sorting operation. Many sorting algorithms, like merge sort or quicksort (depending on the implementation used by the sorting function), require auxiliary space. In the worst case, these algorithms might use an auxiliary array to store elements during the sorting process, and the size of this array can be proportional to the number of people, N, where N is the number of rows in the input costs array. Therefore, the auxiliary space used by the sorting step is O(N).

Edge Cases

Case	How to Handle
Empty input cost array	Return 0 if the input array is empty, as no cost is incurred.
Input array with odd number of costs	Throw an IllegalArgumentException, as the problem requires an even number of costs for pairing cities.
Costs for all employees heavily skewed towards city A	The sorting logic will handle it correctly; after sorting, the first n people will be assigned to city A.
Costs for all employees heavily skewed towards city B	The sorting logic will handle it correctly; after sorting, the first n people will be assigned to city A and the remaining to city B.
Large input array size, potentially causing integer overflow when summing costs	Use a long data type for the total cost variable to prevent potential integer overflow.
Costs are negative numbers	The problem doesn't explicitly disallow negative costs, and the solution (sorting based on cost difference) will still work correctly.
All cost differences are the same (zero or otherwise)	The solution's sorting approach might lead to assigning the first n to A or other valid assignments - the problem doesn't have a single unique optimal answer.
Costs include very large values exceeding practical financial amounts	Ensure chosen data type can hold these values without overflow, e.g., long in Java, or consider if scaling costs down would preserve the relative differences for optimal allocation.