Two City Scheduling

XXX. Two City Scheduling

Greedy

Sorting

Problem Statement:

You are given an array costs where costs[i] = [costA, costB] represents the cost of sending the ith person to city A or city B. There are 2N people, and your goal is to split them such that N people go to each city while minimizing the total cost.

Approach:

1. Start by assuming that everyone is sent to city A. Calculate the total cost of this scenario.
2. Calculate the "refund" for each person if they were switched from city A to city B. This refund is given by cost(B) - cost(A).
3. Sort the refunds in ascending order. A negative refund indicates a cost-saving opportunity, while a positive refund represents additional cost.
4. Select the smallest N refunds to switch N people to city B, thereby minimizing the total cost.
5. Return the updated minimum cost.

Algorithm Intuition:

The key idea is to view the problem as a trade-off:

• Base Cost: Start by sending everyone to city A as the default.
• Opportunity Cost: Calculate the "refund" for each person if they were to switch to city B. This represents the additional cost (or savings) of making the switch.
• Greedy Choice: By sorting the refunds, we ensure that we make the most cost-effective switches first, minimizing the total cost.

Complexity:

Time Complexity: O(n log n), where n is the number of people, due to the sorting step.
Space Complexity: O(n), for the additional array to store refunds.

Java Implementation:

// GREEDY
// Basically you can track all the costs as an opportunity cost
// One way to look at it: Send everyone to city A, and then calculate the difference 
// in cost gained by switching to B for each person.
// The ones with the biggest "refunds" are the ones we should switch first.
public int twoCitySchedCost(int[][] costs) {
    int N = costs.length / 2;
    int[] refund = new int[N * 2];
    int minCost = 0, index = 0;

    // Add up the cost of sending everyone to city A
    for (int[] cost : costs)
        minCost += cost[0];

    // Calculate "refund" gained by switching to city B (cost(B) - cost(A))
    for (int[] cost : costs)
        refund[index++] = cost[1] - cost[0]; // Generate refund values

    // Sort the refunds in ascending order
    Arrays.sort(refund);

    // Switch the first N cities to city B and recalculate the cost
    for (int i = 0; i < N; i++)
        minCost += refund[i]; // Refunds could be negative (cost-saving) or positive

    return minCost;
}