You are driving a vehicle that has capacity empty seats initially available for passengers.  The vehicle only drives east (ie. it cannot turn around and drive west.)
Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off.  The locations are given as the number of kilometers due east from your vehicle's initial location.
Return true if and only if it is possible to pick up and drop off all passengers for all the given trips. 
 
Example 1:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false


Example 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true


Example 3:
Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true


Example 4:
Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true







 



 
Constraints:

trips.length <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000

Difficulty: interview

Starter code:

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        

Solutions:
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        d = defaultdict(int)
        
        for a, b, c in trips:
            d[b] += a
            d[c] -= a
        
        k = 0
        for t in sorted(d.keys()):
            k += d[t]
            if k > capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        from collections import defaultdict
        
        log = defaultdict(int)
        
        for num, start, end in trips:
            log[start] += num
            log[end] -= num
        
        on_bus = 0
        for stop in sorted(log.keys()):
            on_bus += log[stop]
            if on_bus > capacity:
                return False
        
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        timestamp = []
        for trip in trips:
            timestamp.append([trip[1], trip[0]])
            timestamp.append([trip[2], -trip[0]])

        timestamp.sort()

        used_capacity = 0
        for time, passenger_change in timestamp:
            used_capacity += passenger_change
            if used_capacity > capacity:
                return False

        return True

from queue import PriorityQueue

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        sorted_trips = sorted(trips, key=lambda x: (x[1], x[2]))        
        pq = PriorityQueue()
        total_pnum = 0
        
        for trip in sorted_trips:
            pnum, start_loc, end_loc = trip[0], trip[1], trip[2]            
            total_pnum += pnum   
            
            while pq.qsize() > 0:
                prev_end_loc, prev_pnum = pq.get()
                if prev_end_loc > start_loc:                    
                    pq.put((prev_end_loc, prev_pnum))
                    break                    
                total_pnum -= prev_pnum                
                
            if end_loc > start_loc: 
                pq.put((end_loc, pnum))
                
            if total_pnum > capacity: 
                return False
            
        return True

# Time complexity: O(nlogn)
# Time complexity: O(n) for the priorioty queue


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # data = []
        # for t in trips:
        #     data.append((t[1],1, t[0]))
        #     data.append((t[2], 0, t[0]))
        # data = sorted(data)
        # maxp = 0
        # for d in data:
        #     if d[1] == 0:
        #         maxp -= d[2]
        #     else:
        #         maxp += d[2]
        #     if maxp > capacity: return False
        # return True
    
        passenger = 0
        onboard = defaultdict(int)
        offboard = defaultdict(int)
        for t in trips:
            onboard[t[1]] += t[0]
            offboard[t[2]] += t[0]
        for d in range(10001):
            
            if d in onboard: passenger += onboard[d]
            if d in offboard: passenger -= offboard[d]
            if passenger > capacity: return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        if not trips or len(trips) == 0 or capacity == 0:
             return False
        
        # sorting by starting point
        trips.sort(key=lambda x:x[1])
        
        arr = []        
        for num, start, end in trips:
            arr.append([start, num])
            arr.append([end, -num])
        
        arr.sort(key=lambda x:x[0])        
        total = 0
        
        for a in arr:
            total += a[1]
            
            if total > capacity:
                return False
        return True

from queue import PriorityQueue

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        if len(trips) == 0: return True
        
        pq = PriorityQueue()
        total_pnum = 0
        
        for trip in trips:
            pq.put((trip[1], trip[0]))
            pq.put((trip[2], -trip[0]))
        
        while pq.qsize() > 0:
            cur_loc, pnum = pq.get()
            total_pnum += pnum        
                
            if total_pnum > capacity: 
                return False
            
        return True

# Time complexity: O(nlogn)
# Time complexity: O(n) for the priorioty queue


\"\"\"
[[2,1,5],[3,5,7]]
3 return T

[[3,2,8],[4,4,6],[10,8,9]]
11 return T

[[2,1,5],[3,3,7]]
4 return F

[[4, 1, 3], [8, 2, 3], [1, 3, 6], [8, 4, 6], [4, 4, 8]]
12 return F
\"\"\"
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        if not trips: return True
        curr_capacity = capacity
        trips.sort(key=lambda x: (x[1], x[2]))
        print(trips)
        d = collections.defaultdict(list)
        for i, (c, s, e) in enumerate(trips):
            # print(i, c, s, e, d, curr_capacity)
            # if e in d or s in d:
            indexes = []
            # for loc, end_locs in list(d.items():
            for loc in list(d):
                if loc <= s:
                    indexes.extend(d[loc])
                    del d[loc]
                    # indexes = d[s] + d[e]
                    # indexes = d[e]
                    # indexes.extend(d[s])
                    # indexes.ex
                    # print(indexes)
            for index in indexes:
                curr_capacity += trips[index][0]
                    
            curr_capacity -= c
            # print(i)
            if curr_capacity < 0: 
                return False
            d[e].append(i)
            # print(curr_capacity)
        return True

from collections import defaultdict

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        d = defaultdict(int)
        for n, s, e in trips:
            d[s] += n
            d[e] -= n
        
        cur = 0
        for k in sorted(d):
            cur += d[k]
            if cur > capacity: return False
        
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        if not trips or len(trips) == 0 or capacity == 0:
             return False
        
        # sorting by starting point
        trips.sort(key=lambda x:x[1])
        
        arr = []        
        for num, start, end in trips:
            arr.append([start, num])
            arr.append([end, -num])
        
        arr.sort()        
        total = 0
        
        for a in arr:
            total += a[1]
            
            if total > capacity:
                return False
        return True

import heapq
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # print(sorted(x for n, i, j in trips for x in [[i, n], [j, - n]]))
        
        
        for i, v in sorted(x for n, i, j in trips for x in [[i, n], [j, - n]]):
            capacity -= v
            if capacity < 0:
                return False
        return True
        
#         left = capacity
#         h = []
#         trips = sorted(trips, key=lambda x: x[1])
        
#         for t in trips:
#             if h:
#                 while h and t[1] >= h[0][0]:
#                     mint = h[0]
#                     left += mint[1][0]
#                     heapq.heappop(h)
            
#             if left < t[0]:
#                 return False

#             heapq.heappush(h, (t[2], t))
#             left -= t[0]
            
#         return True

#         path = [0] * 1001
#         for t in trips:
#             for i in range(t[1], t[2]):
#                 path[i] += t[0]
#                 if path[i] > capacity:
#                     return False
                
#         return True
            
        


class Solution:
    def carPooling(self, trips: List[List[int]], c: int) -> bool:
        
        f, t = float('inf'), -1
        b = collections.defaultdict(int)
        for n, s, e in trips:
            b[s] += n
            b[e] -= n
    
            f = min(f, s)
            t = max(t, e)
    
        for i in range(f, t + 1):
            b[i] += b[i - 1]
            if b[i] > c:
                return False
        
        return True    


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        timestamp = [0] * 1001
        for trip in trips:
            timestamp[trip[1]] += trip[0]
            timestamp[trip[2]] -= trip[0]

        used_capacity = 0
        for passenger_change in timestamp:
            used_capacity += passenger_change
            if used_capacity > capacity:
                return False

        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips_pickup = sorted(trips,key=lambda x:x[1])
        trips_drop = sorted(trips,key=lambda x:x[2])
        passengers = 0
        i=0
        j=0
        while(i<len(trips)):
            if trips_pickup[i][1] <trips_drop[j][2]:
                passengers +=trips_pickup[i][0]
            else:
                passengers-=trips_drop[j][0]
                j+=1
                continue
            i+=1
            if passengers>capacity:
                return False
        return True

#### dict - get keys - dict.keys()
#### dict initialization : dict [key] = val OR dict = [key:value]

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    
        ## sort trips by starting point to process them in correct order to detect overlap
        trips = sorted(trips, key=lambda x:x[1])
        currentPassengerCt = trips[0][0]
        tripList = dict()
        tripList[trips[0][2]] = trips[0][0]
    
        for idx in range(1,len(trips)):
            numPassengers = trips[idx][0]
            startPt = trips[idx][1]
            endPt = trips[idx][2]

            for prevEndPoint in sorted(tripList.keys()):
                if startPt >= prevEndPoint:
                    ## overlaps with 1 or more trips
                    ## remove finished trips from tripList 
                    ## deduct passengers from currentPassengerCt
                    
                    ## dont overlap with ANY previous trips, capacity <= target    
                    ## reset currentPassengerCt
                    ## empty tripList
                    currentPassengerCt -= tripList[prevEndPoint]
                    del tripList[prevEndPoint]

            ## add current trip to tripList
            ## update currentPassengerCt
            if endPt in tripList:
                tripList[endPt] += numPassengers
            else:
                tripList[endPt] = numPassengers
            currentPassengerCt += numPassengers 

            ## if overlap, then sum(passengers) for all concurrent trips <= capacity
            ## if no overlap, #passengers for trip  <= capacity
            ##  currentPassengerCt exceeded
            if currentPassengerCt > capacity:
                return False

        return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trip_travel=[]
        for passengers,start,end in trips:
            trip_travel.append((start,passengers,1)) #start times so adding people
            trip_travel.append((end,passengers,0)) #start times so removing people
        
        trip_travel.sort(key=lambda x:(x[0],x[2])) #sort and make sure removing people(increase capacity) before adding people - that way if adding and removing at same location-capacity not temporarily < 0 
        for travel in trip_travel:
            if travel[2]==1:
                capacity-=travel[1]
            else:
                capacity+=travel[1]
                
            if capacity<0:
                return False
        
        return True
        
                
        


import heapq

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        
        trips = sorted(trips, key = lambda k: k[1])
        
        
        car_passengers = 0
        drop_location = []
        
        for trip in trips:
            
            passengers, start_location, end_location = trip
            
            car_passengers += passengers
            
            while len(drop_location) != 0 and heapq.nsmallest(1, drop_location)[0][0] <= start_location:
                print(\"hi\")
                passed_location, drop_passengers  = heapq.heappop(drop_location)
                car_passengers -= drop_passengers
                
            heapq.heappush(drop_location, [end_location, passengers])
            
            if car_passengers > capacity:
                return False
            
            car_passengers = max(car_passengers, 0) # don't want 0
            
        return True
        

#### dict - get keys - dict.keys()
#### dict initialization : dict [key] = val OR dict = [key:value]

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    
        ## sort trips by starting point to process them in correct order to detect overlap
        trips = sorted(trips, key=lambda x:x[1])
        currentPassengerCt = trips[0][0]
        tripList = dict()
        tripList[trips[0][2]] = trips[0][0]
    
        for idx in range(1,len(trips)):
            numPassengers = trips[idx][0]
            startPt = trips[idx][1]
            endPt = trips[idx][2]

            #overlap = False
            for prevEndPoint in sorted(tripList.keys()):
                if startPt >= prevEndPoint:
                    ## overlaps with 1 or more trips
                    ## remove finished trips from tripList 
                    ## deduct passengers from currentPassengerCt
                    
                    ## dont overlap with ANY previous trips, capacity <= target    
                    ## reset currentPassengerCt
                    ## empty tripList
                    currentPassengerCt -= tripList[prevEndPoint]
                    del tripList[prevEndPoint]

            ## add current trip to tripList
            ## update currentPassengerCt
            if endPt in tripList:
                tripList[endPt] += numPassengers
            else:
                tripList[endPt] = numPassengers
            currentPassengerCt += numPassengers 

            ## if overlap, then sum(passengers) for all concurrent trips <= capacity
            ## if no overlap, #passengers for trip  <= capacity
            ##  currentPassengerCt exceeded
            if currentPassengerCt > capacity:
                return False

        return True


#### dict - get keys - dict.keys()
#### dict initialization : dict [key] = val OR dict = [key:value]

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    
        ## sort trips by starting point to process them in correct order to detect overlap
        trips = sorted(trips, key=lambda x:x[1])
        currentPassengerCt = trips[0][0]
        tripList = dict()
        tripList[trips[0][2]] = trips[0][0]
    
        for idx in range(1,len(trips)):
            numPassengers = trips[idx][0]
            startPt = trips[idx][1]
            endPt = trips[idx][2]

            #overlap = False
            for prevEndPoint in sorted(tripList.keys()):
                if startPt >= prevEndPoint:
                    ## overlaps with 1 or more trips
                    ## remove finished trips from tripList 
                    ## deduct passengers from currentPassengerCt
                    
                    ## dont overlap with ANY previous trips, capacity <= target    
                    ## reset currentPassengerCt
                    ## empty tripList
                    currentPassengerCt -= tripList[prevEndPoint]
                    del tripList[prevEndPoint]

            ## add current trip to tripList
            ## update currentPassengerCt
            if endPt in tripList:
                tripList[endPt] += numPassengers
            else:
                tripList[endPt] = numPassengers
            currentPassengerCt += numPassengers 

            ## if overlap, then sum(passengers) for all concurrent trips <= capacity
            ## if no overlap, #passengers for trip  <= capacity
            ##  currentPassengerCt exceeded
            print(currentPassengerCt)
            if currentPassengerCt > capacity:
                return False

        return True


#### dict - get keys - dict.keys()
#### dict initialization : dict [key] = val OR dict = [key:value]

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    
        ## sort trips by starting point to process them in correct order to detect overlap
        trips = sorted(trips, key=lambda x:x[1])
        currentPassengerCt = trips[0][0]
        tripList = dict()
        tripList[trips[0][2]] = trips[0][0]
    
        for idx in range(1,len(trips)):
            numPassengers = trips[idx][0]
            startPt = trips[idx][1]
            endPt = trips[idx][2]

            #overlap = False
            for prevEndPoint in sorted(tripList.keys()):
                if startPt >= prevEndPoint:
                    ## overlaps with 1 or more trips
                    ## remove finished trips from tripList 
                    ## deduct passengers from currentPassengerCt
                    currentPassengerCt -= tripList[prevEndPoint]
                    del tripList[prevEndPoint]
                    #overlap = True


            ## dont overlap with ANY previous trips, capacity <= target    
            ## reset currentPassengerCt
            ## empty tripList
            
            #if not overlap:
            #    tripList = []
            #    currentPassengerCt = 0

            ## add current trip to tripList
            ## update currentPassengerCt
            if endPt in tripList:
                tripList[endPt] += numPassengers
            else:
                tripList[endPt] = numPassengers
            currentPassengerCt += numPassengers 

            ## if overlap, then sum(passengers) for all concurrent trips <= capacity
            ## if no overlap, #passengers for trip  <= capacity
            ##  currentPassengerCt exceeded
            print(currentPassengerCt)
            if currentPassengerCt > capacity:
                return False

        return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        import numpy as np
        timestamp = np.zeros(1001)
    
        for trip in trips:
            timestamp[trip[1]:] += trip[0]
            timestamp[trip[2]:] -= trip[0]
        
        if max(timestamp) > capacity:
            return False
        return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    
        def Sort(sub_li): 
            sub_li.sort(key = lambda x: x[1]) 
            return sub_li 
        
        trips = Sort(trips)
        
        people = 0
        on_board = []
        
        for [n,a,b] in trips:
            people +=n
            
            while on_board and on_board[0][1]<=a:
                t = on_board.pop(0)
                people -= t[0]
                
            if people>capacity:
                return False
            
            on_board.append([n,b])
            on_board = Sort(on_board)
            
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        if not trips:
            return 0
        tmp = sorted(x for v, i, j in trips for x in [[i, v], [j, -v]])
        
        n = 0
        for _, v in tmp:
            n += v
            if n > capacity:
                return False
        return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips.sort(key=lambda x: x[1])
        capacity_needed, hp = 0, []
        for trip in trips:
            while hp and hp[0][0]<=trip[1]:
                end,start,c =heapq.heappop(hp)
                capacity_needed-=c
            capacity_needed+=trip[0]
            if capacity_needed>capacity:
                return False
            heapq.heappush(hp,(trip[2],trip[1],trip[0]))
        return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips.sort(key=lambda x : x[1])
        print(trips)
        start=trips[0][1]
        end=trips[0][2]
        capacity=capacity-trips[0][0]
        if(capacity < 0):
            return False
        q=[(trips[0][2],trips[0][0])]
        n=len(trips)
        for trip in trips[1::]:
            s=trip[1]
            dup=q[::]
            while(q):
                if(q[0][0]<=s):
                    capacity+=q[0][1]
                    q.pop(0)
                else:
                    break
            capacity -= trip[0]
            q.append((trip[2],trip[0]))
            q.sort(key = lambda x: x[0])
            if capacity < 0:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips=sorted(trips, key=lambda x:x[1])
        cap=capacity
        st=[]
        for trip in trips:
            if not st:
                if cap<trip[0]:
                    return False
                st.append((trip[0], trip[-1]))
                cap-=trip[0]
            else:
                st=sorted(st, key=lambda x:x[1])
                while st and trip[1]>=st[0][1]:
                    cap+=st[0][0]
                    st.pop(0)
                if cap<trip[0]:
                    return False
                st.append((trip[0], trip[-1]))
                cap-=trip[0]
        return True
                
                    


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips.sort(key = lambda x: x[1])
        length = len(trips)
        
        count = 0
        queue = []
        for trip in trips:
            num_passengers, start_location, end_location = trip
            while queue and queue[0][2] <= start_location:
                count -= queue[0][0]
                queue = queue[1:]
            queue.append(trip)
            queue.sort(key = lambda x: x[2])
            count += num_passengers
            if count > capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        r = True;
        active = [];
        currContent = 0;
        maxCapacity = 0;
        time = 0;
        trips.sort(key=lambda x: x[1]); #sort tips by start time
        lenTrips = len(trips);
        
        #for each trip
        for i in range(0, lenTrips): #figure out the capacity required at the start of each trip
            time = trips[i][1]; #set time to start of ith trip
            
            #add people for ith trip
            currContent += trips[i][0];
            active.append(i);
            
            #remove people for completed trips
            for j in range(len(active)-1, -1, -1):
                if trips[active[j]][2] <= time:
                    currContent -= trips[active[j]][0];
                    active.pop(j);
                    
            #track maximum capacity required
            maxCapacity = max(maxCapacity, currContent);
            
            if maxCapacity > capacity:
                r = False;
                break;
            
        return r;

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # (2,6) (3,5) (4,5)
        sorted_trips = sorted(trips, key=lambda x:x[1])
        in_trip = [sorted_trips[0]]
        cap = capacity - sorted_trips[0][0]
        cur_time = 0
        i = 1        
        while i < len(sorted_trips):
            #print('b', in_trip)
            waiting_passenger = sorted_trips[i]
            if not in_trip:
                cap -= waiting_passenger[0]
                in_trip.append(waiting_passenger)
                #print('add new', waiting_passenger)
                i += 1
                
            else:
                first_passenger = in_trip[0]
                
                if waiting_passenger[1] >= first_passenger[2]:
                    # pop out
                    in_trip.pop(0)
                    cap += first_passenger[0]
                    #print('pop current', first_passenger)
                elif cap >= waiting_passenger[0]:
                    cap -= waiting_passenger[0]
                    in_trip.append(waiting_passenger)
                    in_trip = sorted(in_trip, key=lambda x:x[2])
                    #print('add new', waiting_passenger)
                    i += 1
                else:
                    return False
            #print('a', in_trip)

        return True
                
                
            
            
        


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        sorted_trips = sorted(trips, key=lambda x: x[1])
        print(sorted_trips)
        
        cur_capacity = 0
        left = 0
        location = [0 for i in range(1000 + 1)]
        for trip in trips:
            new_capacity = trip[0]
            new_start, new_end = trip[1], trip[2]
            location[new_start:new_end] = [cap + new_capacity for cap in location[new_start:new_end]]
        # print(location)
        for loc in location:
            if loc > capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        ind = 0
        
        for a,b,c in trips:
            
            ind = max(ind, b, c)
            
        res = [0] * (ind+1)
        
        for a, b, c in trips:
            
            for i in range(b, c):
                res[i] += a
        return not any([x > capacity for x in res])
                    
                
                


class Solution:

    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        def add_list(pool, start, end, num):
            for idx in range(start, end):
                pool[idx] += num
        pool = [0]*1000
        for trip in trips:
            num, start,end = trip
            add_list(pool, start,end, num)
        if max(pool)> capacity:
            return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        occupied = [0 for i in range(1001)]
        for num_passengers, start_location, end_location in trips:
            for i in range(start_location, end_location):
                occupied[i] += num_passengers
        return max(occupied) <= capacity


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        end = 0
        for _,_,e in trips:
            end = max(end, e)

        dp = [0 for _ in range(end)]
        for passengers, start, end in trips:
            for i in range(start, end):
                dp[i] += passengers
        return max(dp) <= capacity

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        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]))
        current=0
        for time,people,pickup in lst:
            if pickup:
                current+=people
            else:
                current-=people
            if current > capacity: return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        
        
        ind = 0
        
        for a,b,c in trips:
            
            ind = max(ind, b, c)
            
        res = [0] * (ind+1)
        
        for a, b, c in trips:
            
            for i in range(b, c):
                res[i] += a
        return not any([x > capacity for x in res])
        
        
            
            
            
        
#         trips.sort(key=lambda x: (x[1], x[2]))
        
#         print(trips)
        
#         pas, start, end = trips[0]
        
#         for i in range(1, len(trips)):
            
#             if trips[i][1] < end:
                
#                 pas += trips[i][0]
#                 if pas > capacity:
#                     return False
#                 end = max(end, trips[i][2])
#             else:
#                 pas = trips[i][0]
#         return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        buckets = [0]*1001
        for trip in trips:
            passengers, start, end = trip
            for i in range(start, end):
                buckets[i] += passengers

        for elem in buckets:
            if elem > capacity:
                return False

        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        self.remainSeats=capacity
        self.tripsOnBoard=[]
        trips = sorted(trips, key=lambda trip:trip[1])
        for trip in trips:
            self.offBoard(trip[1])
            if not self.onBoardTrip(trip):
                return False
        return True
    def offBoard(self, currentLocation: int):
        trips2OffBoard = [trip for trip in self.tripsOnBoard if trip[2]<=currentLocation]
        for trip in trips2OffBoard:
            self.remainSeats += trip[0]
        self.tripsOnBoard = [trip for trip in self.tripsOnBoard if trip[2]>currentLocation]
    
    def onBoardTrip(self, trip: List[int]) -> bool:
        if trip[0]<=self.remainSeats:
            self.remainSeats-=trip[0]
            self.tripsOnBoard.append(trip)
            return True
        else:
            return False


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        #cus_num = [i[0] for i in trips]
        #starts = [i[1] for i in trips]
        ends  = [i[2] for i in trips]
        max_ends = max(ends)
        all_stops = [0 for i in range(0, max_ends+1)]
        #print(all_stops)
        for trip in trips:
            l, r = trip[1], trip[2]
            #print(all_stops)
            all_stops[l:r] = [i + trip[0] for i in all_stops[l:r] ]
            if max(all_stops[l:r]) > capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:

        final = 0

        for trip in trips:
            final = max(final, trip[2])
        people = [0] * (final + 1)

        for trip in trips:
            for board in range(trip[1], trip[2]):
                people[board] += trip[0]

        if max(people) > capacity:
            return False        
        else:
            return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        total_trip = [0 for _ in range(1000)]
        for tt in trips:
            for loc in range(tt[1],tt[2]):
                total_trip[loc] += tt[0]
        if max(total_trip) <= capacity:
            return True
        return False

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        dests = [x[2] for x in trips]
        myl = [0 for i in range(max(dests)+1)]
        for x in trips:
            for c in range(x[1], x[2]):
                myl[c] += x[0]
        
        for i in myl:
            if i>capacity:
                return False
            
        return True
        


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # trips: List[[num_passengers, start_idx, end_idx]]
        # for each position, count number of people required
        
        n = len(trips)
        
        # 1. arrange trips by start date
        sorted_trips = sorted(trips, key=lambda t: t[1])
        
        # 2. for min_idx, max_idx keep track of all active trips overlapping
        min_idx = sorted_trips[0][1]
        max_idx = max([t[2] for t in sorted_trips])
        
        merged = [0 for _ in range(max_idx + 1)]
        
        # base case
        for num_passenger, start_idx, end_idx in sorted_trips:
            for idx in range(start_idx, end_idx):
                merged[idx] += num_passenger
                if merged[idx] > capacity:
                    # print(f\"merged={merged}; idx={idx}\")
                    return False
        
        return True
            


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips = sorted(trips, key=lambda x: x[1])
        curr = []
        
        for i in trips:
            
            curr.append([i[0], i[2]])
            
            s = 0
            for c in curr:
                if c[1] <= i[1]:
                    continue
                s += c[0]
            
            if s > capacity:
                return False
        
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        d=[0 for i in range(1001)]
        for i in trips:
            for j in range(i[1], i[2]):
                d[j]+=i[0]
        # print(d)
        for i in range(1001):
            if d[i]>capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
#         # time O(max(N, 1001)); space O(1001)
#         timestamp = [0] * 1001
#         for trip in trips:
#             timestamp[trip[1]] += trip[0]
#             timestamp[trip[2]] -= trip[0]
        
#         used = 0
#         for change in timestamp:
#             used += change
#             if used > capacity:
#                 return False
            
#         return True

        # time O(nlogn); space O(n)
        pooling = []
        for num, start, end in trips:
            pooling.extend([[start, num], [end, -num]])
        pooling.sort()
        
        for loc, num in pooling:
            capacity -= num
            if capacity < 0:
                return False
        return True

from collections import defaultdict, OrderedDict
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips = sorted(trips, key=lambda x: x[1])
        passengers = 0
        
        dropoffs = defaultdict(int)
        for i in range(len(trips)):
            dropoffs[trips[i][2]] += trips[i][0]
        dropoffs = OrderedDict(sorted(dropoffs.items()))

        for lis in trips:
            passengers += lis[0]
            for key in dropoffs:
                if lis[1] >= key:
                    passengers -= dropoffs[key]
                    dropoffs[key] = 0
            # print(passengers)
            if passengers > capacity:
                return False
        return True
            
        


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        load = [0] * 1001
        for count, from_idx, to_idx in trips:
            for i in range(from_idx, to_idx):
                load[i] += count
                if load[i] > capacity:
                    return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        passengers = [0] * 1000
        
        for trip in trips:
            p, start, end = trip
            for i in range(start, end):
                passengers[i] += p
                if passengers[i] > capacity:
                    return False
        return True


class Solution:

    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        def add_list(pool, start, end, num):
            for idx in range(start, end):
                pool[idx] += num
                if pool[idx] > capacity:
                    return False
        pool = [0]*1000
        for trip in trips:
            num, start, end = trip
            is_false = add_list(pool, start, end, num)
            if is_false == False:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        
        \"\"\"
        [[2,1,5],[3,3,7]]
        
        1 2 3 4 5 6 7
        2 2 2 2 2
        2 2 5 2 2        
        
        c = 4
        \"\"\"
            
        count_vec = [0]*1001
                        
        for num_pass, start, end in trips:
            for i in range(start, end):
                count_vec[i] += num_pass
                if count_vec[i] > capacity:
                    return False
                
        return True
        


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        totals = [0] * 1001
        for (passengers, start, end) in trips:
            for x in range(start, end):
                totals[x] += passengers
                if totals[x] > capacity:
                    return False
        return True

from operator import itemgetter

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        cp_arr = []
        print(trips)
        trips = sorted(trips, key=lambda x: x[1], reverse=False)
        print(trips)
        min_val = min([i[1] for i in trips])
        max_val = max([i[2] for i in trips])
        offset = max_val - min_val
        print(f\"max:{max_val} min:{min_val}\")
        check_arr = [0] * offset
        print(check_arr)
        
        for trip in trips:
            low = trip[1]
            high = trip[2]
            for i in range(low, high):
                check_arr[i - offset] += trip[0]
        
        print(check_arr)
        
        if max(check_arr) <= capacity:
            return True
        return False

from operator import itemgetter

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        cp_arr = []
        trips = sorted(trips, key=lambda x: x[1], reverse=False)
        min_val = min([i[1] for i in trips])
        max_val = max([i[2] for i in trips])
        offset = max_val - min_val
        check_arr = [0] * offset
        
        for trip in trips:
            low = trip[1]
            high = trip[2]
            for i in range(low, high):
                check_arr[i - offset] += trip[0]

        if max(check_arr) <= capacity:
            return True
        return False

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        dp = [capacity] * 1000
        for trip in trips:
            for loc in range(trip[1], trip[2]):
                dp[loc] -= trip[0]
        return not (min(dp) < 0)


from operator import itemgetter
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        #trips = sorted(trips,key=itemgetter(2))
        dp = [0] * 1001
        for t in trips:
            for j in range(t[1],t[2]):
                dp[j] += t[0]
                #print(dp)
                if dp[j] > capacity:
                    return False
    
        return True

class Solution:
    \"\"\"
    return false when a pickup exceeds capacity
    pickup & drop off can happen at same location
    [2,1,5]
    car = 4, 4, 
    
    
    create pickup_dict = {start_location : [[num_passenger = trip[0], end_location=trip[2]]]}
    dropoff_dict = {drop_off location : num_passengers}
    car = [0]*capacity
    car is full when all elem in car > 0
    
    for location in locations:
        decement remaining for passengers in car (make sure no negatives)
        check if location is a pickup:
            if capacity full:
                return false
            else:
                update car
    return True
    
    \"\"\"
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        pickups = {} # start location : [[num_passengers]
        drops = {} # drop location: num
        for trip in trips:
            pickups[trip[1]] = pickups.get(trip[1], 0)+trip[0]
            drops[trip[2]] = drops.get(trip[2],0)+trip[0]
        
        count_passengers = 0
        for start in range(1001):
            if start in pickups.keys():
                count_passengers += pickups[start]
                # increment passenger count
            if start in drops.keys():
                count_passengers -= drops[start]
            if count_passengers > capacity:
                return False
        return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        count_pass = trips[len(trips)-1][2]*[0]
        for i in trips:
            if len(count_pass)< i[2]:
                count_pass += [0]*(i[2]-len(count_pass))
            for j in range(i[1],i[2]):
                count_pass[j] += i[0] 
                if count_pass[j]> capacity:
                    return False
        return True


from operator import itemgetter
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips = sorted(trips,key=itemgetter(2))
        dp = [0] * (trips[-1][2]+1)
        for t in trips:
            for j in range(t[1],t[2]):
                dp[j] += t[0]
                #print(dp)
                if dp[j] > capacity:
                    return False
    
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        cap = [capacity]*1000
        for trip in trips:
            for i in range(trip[1], trip[2]):
                cap[i] -= trip[0]
                if cap[i] < 0:
                    return False
        return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        if len(trips) <=0:
            return False
        
        trips.sort(key = lambda x : x[1]) # Sorting array by start time
        stack = [] # maintaing list to store indexes so that we can compare start time of previous and with current end time
        if trips[0][0] > capacity:
            return False
        else:
            stack.append(0)
            capacity-=trips[0][0]
            
        for i in range(1, len(trips)):
            n = 0
            # if current start time >= any one of previous indices start time--> inc capacity
            while stack and n < len(stack): 
                if trips[i][1] >= trips[stack[n]][2]:
                    capacity += trips[stack[n]][0]
                    stack.pop(n)
                else: n+=1
                
            if trips[i][0] <= capacity:
                capacity-=trips[i][0]
            elif trips[i][0] > capacity:
                return False
            stack.append(i)
        return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips = sorted(trips, key = lambda x : x[1])
        
        pos = 0
        curr_capacity = capacity
        ht = {} # drop off location : passengers
        for trip in trips:
            # if dropOff < trip[1]:
            #     curr_capacity -= 
            # elif trip[0] > curr_capacity:
            #     return False
            for prev in ht:
                if prev <= trip[1]:
                    curr_capacity += ht[prev]
                    # del ht[prev]
                    ht[prev] = 0
            
            if trip[0] > curr_capacity:
                return False
            
            if trip[2] not in ht:
                ht[trip[2]] = trip[0]
            else:
                ht[trip[2]] += trip[0]
            
            curr_capacity -= trip[0]
        
        return True
              


class Solution:
#     def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
#         curr_end, max_end = 0, 0
#         list_curr = []
#         for trip in trips:
#             max_end = trip[2]
#             list_curr.extend([0] * (max_end - curr_end))
#             # print(len(list_curr))
#             for _ in range(trip[1], trip[2]):
#                 list_curr[_] += trip[0]
#             curr_end = max_end
            
#             if max(list_curr) > capacity:
#                 return False
#         return True
    # def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    #     list_end = []
    #     for _ in trips:
    #         list_end.extend([_[2]])
    #     len_list = max(list_end)
    #     list_curr = [0]*len_list
    #     for trip in trips:
    #         for _ in range(trip[1], trip[2]):
    #             list_curr[_] += trip[0]
    #         if max(list_curr) > capacity:
    #             return False
    #     return True
    
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        list_curr = [0]*1000
        for trip in trips:
            for _ in range(trip[1], trip[2]):
                list_curr[_] += trip[0]
            if max(list_curr) > capacity:
                return False
        return True
        
    
            
            


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trip_start = min([trip[1] for trip in trips])
        trip_end = max([trip[2] for trip in trips])
        
        trip_register = [0]*(trip_end+1)
        for trip in trips:
            for idx in range(trip[1], trip[2]):
                trip_register[idx] += trip[0]
        
        return capacity >= max(trip_register)

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        
        m = [ 0 for i in range(1000)]
        
        for x in trips:
            if  x[0] > capacity:
                return False
            
            for i in range(x[1],x[2]):
                m[i]+=x[0]
            
            if max(m)> capacity:
                return False
        
        if max(m) > capacity:
            return False
        return True
                


import heapq
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        
#         left = capacity
#         h = []
#         trips = sorted(trips, key=lambda x: x[1])
        
#         for t in trips:
#             if h:
#                 while h and t[1] >= h[0][0]:
#                     mint = h[0]
#                     left += mint[1][0]
#                     heapq.heappop(h)
            
#             if left < t[0]:
#                 return False

#             heapq.heappush(h, (t[2], t))
#             left -= t[0]
            
#         return True

        path = [0] * 1001
        for t in trips:
            for i in range(t[1], t[2]):
                path[i] += t[0]
                if path[i] > capacity:
                    return False
                
        return True
            
        


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        pickups = sorted([lst[:2] for lst in trips], key = lambda lst : lst[1])
        dropoffs = sorted([lst[::2] for lst in trips], key = lambda lst: lst[1])
        print(pickups, dropoffs)
        
        currentCap = 0
        i, j = 0, 0
        nextP, nextD = pickups[0], dropoffs[0]
        while i < len(pickups):
            if nextP[1] < nextD[1] or not nextD:
                currentCap += nextP[0]
                i += 1
                if i < len(pickups):
                    nextP = pickups[i]
                else:
                    nextP = None
            elif nextP[1] > nextD[1] or not nextP:
                currentCap -= nextD[0]
                j += 1
                if j < len(dropoffs):
                    nextD = dropoffs[j]
                else:
                    nextD = None
            else:
                currentCap += nextP[0] - nextD[0]
                i += 1
                j += 1
                if i < len(pickups):
                    nextP = pickups[i]
                else:
                    nextP = None
                if j < len(dropoffs):
                    nextD = dropoffs[j]
                else:
                    nextD = None
                
            print(i, j, currentCap)
            if currentCap > capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips.sort(key=lambda x: x[1] )
        last_dest = max([x[2] for x in trips])
        curr_pos = 0
        
        cap_ls = [0] * last_dest
        for i in range(len(trips)):
            for j in range(trips[i][1], trips[i][2]):
                cap_ls[j] += trips[i][0]
        
        return max(cap_ls) <= capacity

            


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        ans_dic = [0]*1000
        for i in trips:
            for j in range(i[1], i[2]):
                if ans_dic[j]:
                    ans_dic[j] += i[0]
                    if ans_dic[j] > capacity:
                        return False
                else:
                    ans_dic[j] = i[0]
        # print(ans_dic)
        return True



class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        totals = [0] * 1001
        for (passengers, start, end) in trips:
            for x in range(start, end):
                totals[x] += passengers
        return not any([x > capacity for x in totals])

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        counter = [0]* 1000
        for elem in trips:
            for i in range(elem[1], elem[2]):
                counter[i] += elem[0]
        if max(counter) > capacity:
            return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        n = len(trips)
        dp = [0]*1000
        
        for trip in trips:
            num, s, e = trip[0], trip[1], trip[2]
            for i in range(s, e):
                dp[i] += num
        print(dp)
        for i in range(len(dp)):
            if dp[i] > capacity:
                return False
            
        return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
      milesDict = {}

      for trip in trips:
        passengers = trip[0]
        start = trip[1]
        end = trip[2]

        mile = start

        while mile < end:
          if mile in milesDict:
            milesDict[mile] = milesDict[mile] + passengers
          else:
            milesDict[mile] = passengers

          mile = mile + 1

      if max(milesDict.values()) <= capacity:
        return True
      else:
        return False


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        d=dict()
        ppl=0        
        for i in trips:
            d[i[1]]=d.get(i[1],0)+i[0]
            for j in range(i[1]+1,i[2]):
                d[j]=d.get(j,0)+i[0]
        for i in list(d.values()):
            if i>capacity:
                return False
        return True
        
        
            


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        d={}
        for i in trips:
            for j in range(i[1]+1,i[2]+1):
                if j not in d:
                    d[j]=i[0]
                else:
                    d[j]+=i[0]
        #print(d)
        for i in d:
            if d[i]>capacity:
                return 0
        return 1


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        kmlist = {}
        trips.sort(key=lambda x: (x[1], x[2]))
        for trip in trips:
            for i in range(trip[1], trip[2]):
                if i in kmlist:
                    kmlist[i] += trip[0]
                else:
                    kmlist[i] = trip[0]
        maxval = max(kmlist.values())
        return maxval <= capacity
                    



class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
          milesDict = {}
          for trip in trips:
            passengers = trip[0]
            start = trip[1]
            end = trip[2]
            mile = start
            while mile < end:
              if mile in milesDict:
                milesDict[mile] = milesDict[mile] + passengers
              else:
                milesDict[mile] = passengers
              mile = mile + 1
          if max(milesDict.values()) <= capacity:
            return True
          else:
            return False

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        events = [[x[1],x[0]] for x in trips] + [[x[2],-x[0]] for x in trips]
        events.sort()
        n = 0
        for event in events:
            n += event[1]
            if n > capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # create a array res, res[i] == passenger at place i
        # go through list and add trips[0] to [trips[1], trips[2])
        # check if max(res) <= capacity, if not, false
        
        res = [0]*1000
        
        for trip in trips:
            passenger, start,end = trip
            for i in range(start,end):
                res[i]+= passenger
        return max(res) <=capacity 

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        if not trips:
            return True
        firstStop = 1001
        lastStop = -1
        for trip in trips:
            firstStop = min(firstStop, trip[1])
            lastStop = max(lastStop, trip[2])
        stops = [0] * (lastStop-firstStop+1)
        for trip in trips:
            for i in range(trip[1], trip[2]):
                stops[i-firstStop] += trip[0]
                if stops[i-firstStop] > capacity:
                    return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        p_list = list()
        for p, s, e in trips:
            if len(p_list) < e:
                p_list += [0]*(e - len(p_list))
            for i in range(s, e):
                p_list[i] += p
                if p_list[i] > capacity:
                    return False
        
        return True

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

            timeline = {}
            for trip in trips:
                for t in range(trip[1], trip[2]):
                    timeline[t] = timeline.get(t, 0) + trip[0]

            for t in timeline:
                if timeline[t] > capacity:
                    return False
            return True
        return car_pooling(trips, capacity)

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        ma = float('-inf')
        trips = sorted(trips, key=lambda v: v[1])
        for i in range(len(trips)):
            tmp = 0
            for j in range(i+1):
                if trips[j][2] > trips[i][1]:
                    tmp += trips[j][0]
            ma = max(tmp, ma)
        return ma <= capacity

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        passIn = [[item[1],item[0]] for item in trips]
        passOut = [[item[2],-item[0]] for item in trips]
        setOfTimes = list(set([item[1] for item in trips]+[item[2] for item in trips]))
        setOfTimes.sort()
        ans = True
        counter = 0
        for time in setOfTimes:
            if ans == True:
                for item in passIn+passOut:
                    if item[0] == time:
                        counter += item[1]
                if counter>capacity:
                    ans = False
        return ans


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        d = {}
        for (passengers, start, end) in trips:
            for i in range(start, end):
                if d.get(i) == None:
                    d[i] = passengers
                else:
                    d[i] += passengers

        for x in d:
            if d[x] > capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        end = 0
        inCar = 0
        for i in range(0,len(trips)):
            if trips[i][2] > end:
                end = trips[i][2]
        for i in range(1,end):
            for item in trips:
                if item[2] == i:
                    inCar -= item[0]
                elif item[1] == i:
                    inCar += item[0]
            if inCar > capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        d = {}
        for (passengers, start, end) in trips:
            # print(passengers, start, end)
            for i in range(start, end):
                if d.get(i) == None:
                    d[i] = passengers
                    # print(d[i])
                else:
                    d[i] += passengers
                    # print(d[i])

        for x in d:
            if d[x] > capacity:
                return False
        return True

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        
        
        trips.sort(key = lambda x: x[1])
        heap = []
        cur = 0
        
        for pas, start, end in trips:
            
            while heap and heap[0][0] <= start:
                cur -= heappop(heap)[1]
            
            heappush(heap, (end, pas))
            cur += pas
            if cur > capacity:
                return False
        return True