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
Constraints:
2 * n == costs.length2 <= costs.length <= 100costs.length is even.1 <= aCosti, bCosti <= 1000This approach relies on sorting the people by the difference between the cost of flying them to city A and city B. By doing so, we can initially assume that flying every person to city A is optimal, and then we adjust half of the people to go to city B based on minimal added cost.
In this solution, we first sort the list of costs based on the difference between the cost of city A and city B for each person. The comparison function is used with qsort. Then, we add the cost for city A for the first half of people and the cost for city B for the second half of people, returning the total minimized cost.
C++
Java
Python
C#
JavaScript
The time complexity of this solution is O(n log n) due to the sorting step, and the space complexity is O(1) since we are sorting in place.
Two City Scheduling - Leetcode 1029 - Python • NeetCode • 29,403 views views
Watch 9 more video solutions →Practice Two City Scheduling with our built-in code editor and test cases.
Practice on FleetCode