Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

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.
Copy the code

Note:

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

parsing

The company plans to interview 2n people. Given an array costs, where costs[I] = [aCosti, bCosti], means that the cost of the ith person flying to city A is aCosti, and that of the ith person flying to city B is bCosti.

Return the minimum cost of flying everyone to one of the cities in A or B, requiring n people to arrive in each city.

If we first transport all the people to B, and then select N people and then transport them to A, if we want to change one person’s journey, the company will bear the cost of aCosti – bCosti, and then order them in ascending order. Arrange the first N people to fly to A, and then the last N people to fly to B, add up all the costs and return.

The time complexity is O(NlogN), and the space complexity is O(1).

answer

class Solution(object):
    def twoCitySchedCost(self, costs):
        N = len(costs)
        result = 0
        costs.sort( key = lambda x : x[0] - x[1] )  
        for i in range(N//2):
            result += costs[i][0] + costs[i+N//2][1]
        return result	
Copy the code

The results

Given in the Python online submission for Two City Scheduling. The linked submissions in the Python online list for Two City Scheduling.Copy the code

The original link

Leetcode.com/problems/tw…

Your support is my biggest motivation