LC 1094 [M] Car Pooling - ALawliet/algorithms GitHub Wiki
class Solution:
def carPooling2(self, trips: List[List[int]], capacity: int) -> bool: # O(nlogn), kind of like meeting rooms
lst = []
for people, st, end in trips:
lst.append( (st,people,1) )
lst.append( (end,people,0) )
lst.sort(key=lambda x: (x[0],x[2])) # drop off earliest end first
current = 0
for time, people, pickup in lst:
if pickup:
current += people
else:
current -= people
if current > capacity: return False
return True
def carPooling(self, trips: List[List[int]], capacity: int) -> bool: # O(n)
m = max([e for _,_,e in trips])
lookup = [0] * (m+2) # time before and time after extra buffer
# track how many people are in the car at a time and see if any exceed
for people,st,end in trips:
lookup[st+1] += people
lookup[end+1] -= people
return max(accumulate(lookup)) <= capacity # prefix/rolling sum accumulate people because the car can stack up