Leetcode 1094. Car Pooling

Problem

Leetcode 1094 - Car Pooling

Example:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

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

Approach

We can sort by trips[1] (from) position so that we can take in people in the car in order.

Once capacity reaches -1 or below then we can return false.

Else, we can increment capacity when people leave the car.

Here is the Python code for the solution:

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        newTrips = []
        for num, f, t in trips:
            newTrip.append([f,t,num])

        heapq.heapify(newTrips)
        to = defaultdict(list)
        time = 0

        while newTrips:
            if capacity < 0:
                return False

            f, t, num = heapq.heappop(newTrips)
            for i in range(time, f+1):
                if i in to:
                    while to[i]:
                        capacity += to[i].pop()

            to[t].append(num)
            time = f
            capacity -= num

        return capacity >= 0    

Time Complexity and Space Complexity

Time Complexity: $O(n log n)$

Space Complexity: $O(n)$