Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1029 with 12 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1029 # by problem number
lcpy gen -s two_city_scheduling # by problem name
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.
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.
Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859
Explanation: For example, the way to achieve the minimum of 1859 is:
- Fly the 1st person (259, 770) to city A for 259.
- Fly the 2nd person (448, 54) to city B for 54.
- Fly the 3rd person (926, 667) to city B for 667.
- Fly the 4th person (184, 139) to city B for 139.
- Fly the 5th person (840, 118) to city B for 118.
- Fly the 6th person (577, 469) to city A for 577.
The total minimum cost is 1859.
Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086
Explanation: The total minimum cost is 3086.
2 * n == costs.length2 <= costs.length <= 100costs.length is even.1 <= aCosti, bCosti <= 1000class Solution:
# Time: O(n log n)
# Space: O(n) for the sorted copy
def two_city_sched_cost(self, costs: list[list[int]]) -> int:
ordered = sorted(costs, key=lambda cost: cost[0] - cost[1])
n = len(ordered) // 2
return sum(cost[0] for cost in ordered[:n]) + sum(cost[1] for cost in ordered[n:])
| Time | Space |
|---|---|
| O(n log n) | O(n) for the sorted copy |