MediumNo. 1029
Two City Scheduling — LeetCode 1029 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
costs.sort(key=lambda x: x[0] - x[1])
n = len(costs) >> 1
return sum(costs[i][0] + costs[i + n][1] for i in range(n))Complexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1029. Two City Scheduling is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0179 | Largest Number | Medium |
| 0324 | Wiggle Sort II | Medium |
| 0452 | Minimum Number of Arrows to Burst Balloons | Medium |
| 0455 | Assign Cookies | Easy |
| 0502 | IPO | Hard |
| 0561 | Array Partition | Easy |
Frequently asked questions
- How hard is LeetCode 1029. Two City Scheduling?
LeetCode 1029. Two City Scheduling is rated Medium on LeetCode.
- What topics does LeetCode 1029. Two City Scheduling cover?
LeetCode 1029. Two City Scheduling is tagged Greedy, Array and Sorting on LeetCode.