Lc1094

from heapq import heappush, heappop
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    # time O(NlgN) space O(2N)
        if not trips:
            return False
        pq = []
        for pp, start, end in trips:
            heappush(pq,(start,pp))
            heappush(pq,(end,-pp))
        while pq:
            capacity -= heappop(pq)[1]
            if capacity < 0:
                return False
        return True

class Solution:
# time O(1001

+N) space O(1001)
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:

        bucket = [0] * 1001
        for trip in trips:
            bucket[trip[1]] += trip[0]
            bucket[trip[2]] -= trip[0]
        cur_capacity  = 0
        for b in bucket:
            cur_capacity += b
            if cur_capacity > capacity:
                return False
        return True