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