Two City Scheduling

LeetCode Problem #1029 (Medium)

Problem Statement

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

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

Note:

1 <= costs.length <= 100

costs.length is even.

1 <= costs[i][0], costs[i][1] <= 1000

Testcase

Input: [[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.

Problem Explanation

A particular cost is incurred when an individual is sent to one of two cities—City A or City B for an interview. The costs are given in a two-dimensional vector where each vector inside it represents the travel cost for every person.

The first value in the vector is the cost of sending a person to City A.

The second value in the vector is the cost of sending a person to City B.

Out of the total number of people (2N), we can only send half to each city (N). We must calculate the optimum (minimum) cost that can be generated by sending people to either of the two cities.

Algorithm

Difference of Costs Approach

In this approach, we calculate the difference between sending a person to City A and sending the person to City B to see if there is a profit in sending the person to one city over another.

Since only half the people can go to each city, we sort the list of people based on this value of profit and send the first half to City A and send the second half to City B such that we gain maximum profit by doing so.

1. Calculate the cost of sending every person to City A and store it in a variable.

2. Calculate the difference between sending a person to City B instead of City A, and store it in an array.

3. Sort the values in the array. The smaller the difference value, the greater the profit earned by sending them to City B.

4. Choose the first N people from the array (the ones having lowest difference value) and send them to City B.

5. Add the difference of the cost of sending people to City B instead of City A to the original total cost.

Example:

Consider the input array:

[[10,20],[30,200],[400,50],[30,20]]

• Add the cost of sending each person to City A. This value is the first value in the vector.

minCost = 10 + 30 + 400 + 30 = 470

• Calculate the difference or "refund" that would be incurred if each person is sent to City B instead of City A. This can be done by subtracting the first value in the vector from the second value.

20 - 10 = 10
200 - 30 = 170
50 - 450 = -350
20 - 30 = -10

• Sort the refund values in ascending order.

-350, -10, 10, 170

• The smaller the value, the greater the profit gained by sending the person to City B instead of City A. Choose the first N people out of the total 2N people to send to City B as stipulated by the question.

-350, -10

• Add these values to the originally obtained minCost to calculate the total minimum cost.

470 + (-350) + (-10) = 110

Time Complexity: O(nlogn)

Code

int twoCitySchedCost(vector<vector<int>>& costs) {
    // A vector stores the difference between sending a person to City B instead of City A
    vector<int> refund;
    // Total number of people = 2N
    int N = costs.size() / 2;
    // minCost tracks the minimum total cost of sending people to each city
    int minCost = 0;
    
    for(vector<int> cost: costs) {
        // Accumulate the cost of sending each person to City A
        minCost += cost[0];
        // Store the value of the difference between sending a person to City B instead of City A as the refund
        refund.push_back(cost[1] - cost[0]);
    }
    
    // Sort the refund vector in ascending order
    sort(refund.begin(), refund.end());
    
    // Add the refund value for n people with the minimum cost acquired
    for(int i = 0; i < N; i++) {
        minCost += refund[i];
    }
        
    // Return the minimum possible cost for sending each person to their respective cities
    return minCost;
}