Solution For Two City Scheduling

The Two City Scheduling problem on LeetCode is a problem in which we are given a list of costs, which represent the cost of sending a person to one of two different cities. We have to find the minimum cost of sending all the people to two different cities such that an equal number of people are sent to each city.

To solve this problem, we can use the following steps:

Step 1: Sort the list of costs in increasing order.

Step 2: Divide the list of costs into two equal parts, such that the first half represents the cost of sending people to the first city and the second half represents the cost of sending people to the second city.

Step 3: Calculate the total cost of sending all the people to the first city and the total cost of sending all the people to the second city.

Step 4: Return the minimum of the two total costs.

Here is the Python code for the Two City Scheduling problem using the above steps:

“`
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
# Sort the list of costs in increasing order
costs.sort(key=lambda x: x[1] – x[0])

    # Divide the costs into two equal parts
    n = len(costs) // 2

    # Calculate the total cost of sending all the people to the first city
    total_cost_a = sum(x[0] for x in costs[:n])

    # Calculate the total cost of sending all the people to the second city
    total_cost_b = sum(x[1] for x in costs[n:])

    # Return the minimum of the two total costs
    return total_cost_a + total_cost_b

“`

The time complexity of this solution is O(nlogn), where n is the length of the list of costs, due to the sorting of the list. The space complexity is O(1) since we are using constant extra space.

Step by Step Implementation For Two City Scheduling

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        // sort by a cost difference between city A and city B
        Arrays.sort(costs, (a, b) -> Integer.compare(a[0] - a[1], b[0] - b[1]));
        // A send half of people to city A, B send all to city B
        int cost = 0;
        for (int i = 0; i < costs.length / 2; i++) {
            cost += costs[i][0];
        }
        for (int i = costs.length / 2; i < costs.length; i++) {
            cost += costs[i][1];
        }
        return cost;
    }
}

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        # sort the costs in increasing order of the difference between the costs of the 2 cities
        # this will ensure that we send as many people as possible to the cheaper city first
        # and only send people to the more expensive city when absolutely necessary
        costs.sort(key = lambda x: x[0] - x[1])
        
        # the cost of sending the first half of the people to city A
        # and the second half of the people to city B
        # is simply the sum of the first half of the costs + the second half of the costs
        # since we've sorted the costs in order of increasing difference,
        # the first half of the costs will be the costs of city A
        # and the second half will be the costs of city B
        cost = 0
        for i in range(len(costs)//2):
            cost += costs[i][0]
        for i in range(len(costs)//2, len(costs)):
            cost += costs[i][1]
        return cost

var twoCitySchedCost = function(costs) {
    
    // sort by the difference in cost between city A and city B
    // if the difference is negative, it means that it's cheaper to fly to city B
    // if the difference is positive, it means that it's cheaper to fly to city A
    
    costs.sort((a, b) => Math.abs(b[0] - b[1]) - Math.abs(a[0] - a[1]))
    
    // keep track of the total cost
    let totalCost = 0
    
    // keep track of the number of people flying to city A and city B
    let numA = 0
    let numB = 0
    
    // iterate through the sorted costs
    for (let i = 0; i < costs.length; i++) {
        
        // if it's cheaper to fly to city A, add the cost to the total and increment the number of people flying to city A
        if (costs[i][0] < costs[i][1]) {
            totalCost += costs[i][0]
            numA++
        } 
        // if it's cheaper to fly to city B, add the cost to the total and increment the number of people flying to city B
        else {
            totalCost += costs[i][1]
            numB++
        }
        
        // if we have reached the halfway point, stop iterating
        if (numA == costs.length / 2 || numB == costs.length / 2) {
            break
        }
    }
    
    return totalCost
};

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.

 

Example 1:

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.
 

Note:

1 <= costs.length <= 100
It is guaranteed that costs.length is even.
1 <= costs[i][0], costs[i][1] <= 1000

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.

 

Example 1:

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.
 

Note:

1 <= costs.length <= 100
It is guaranteed that costs.length is even.
1 <= costs[i][0], costs[i][1] <= 1000