# LeetCode: 1094. 拼车¶

## 1、题目描述¶

• 必须接送的乘客数量；
• 乘客的上车地点；
• 以及乘客的下车地点。

输入：trips = [[2,1,5],[3,3,7]], capacity = 4



输入：trips = [[2,1,5],[3,3,7]], capacity = 5



输入：trips = [[2,1,5],[3,5,7]], capacity = 3



输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11



• 你可以假设乘客会自觉遵守 “先下后上” 的良好素质
• trips.length <= 1000
• trips[i].length == 3
• 1 <= trips[i][0] <= 100
• 0 <= trips[i][1] < trips[i][2] <= 1000
• 1 <= capacity <= 100000

## 2、解题思路¶

• 按照上车位置排序
• 将下车位置与人数保存到栈中，每次遇到一个上车点，判断是否有人下车，保证最大的空位
import heapq

class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
trips.sort(key=lambda x: (x[1], x[2]))

cur_capacity = capacity
get_off = []

for num_passengers, start_location, end_location in trips:

while get_off and get_off[0][0] <= start_location:
end_location_temp, nums = heapq.heappop(get_off)
cur_capacity += nums
if cur_capacity >= num_passengers:
cur_capacity -= num_passengers
heapq.heappush(get_off, [end_location, num_passengers])
else:
return False

return True