Car Pooling - Leetcode Solution

Problem statement:

There are n drivers in a city. Each driver has a car, and each car has a maximum capacity of seats available for passengers, including the driver's seat. The city has m pickup points where passengers can request a ride.

You are given a list of integer arrays trips, where trips[i] = [num_passengersi, pickup_i, dropoff_i] contains information about the i-th trip: the number of passengers that need to be picked up, and the pickup and dropoff locations.

The locations are given as the number of kilometers due east from the city center. The car for the i-th driver starts at the location trips[i][1] and can transport up to trips[i][0] passengers. The i-th trip starts at the location pickup_i and ends at the location dropoff_i.

You need to determine whether it is possible for all the given trips to be completed by some subset of the drivers and their cars.

Solution:

Approach 1: Brute force

The brute force approach would be to generate all possible combinations of drivers and trips and check if there exists a combination where all trips can be completed.

The time complexity of this approach would be O(2^N) where N is the number of drivers because we need to generate all possible combinations of drivers.

Approach 2: Sorting and Greedy

We can sort the trips based on their pickup location, i.e., in increasing order of pickup_i. Then, we can iterate through each trip and check if there exists a driver whose car has enough seats available for passengers and whose current location is less than or equal to the pickup location of the current trip.

We can maintain a priority queue of drivers based on their dropoff location. Whenever we assign a trip to a driver, we can add the driver to the priority queue based on their dropoff location.

We can iterate through each trip and check if there exists a driver whose car has enough seats available for passengers and whose current location is less than or equal to the pickup location of the current trip. If we find such a driver, we assign the trip to the driver, and update their current location and the number of available seats in their car. We also add the driver to the priority queue based on their dropoff location.

If we cannot find a driver for a trip, we return False. Otherwise, if we are able to assign all the trips, we return True.

Time complexity: O(NlogN) where N is the number of drivers because we need to sort the trips and use a priority queue. Space complexity: O(N) for the priority queue.

Solution code:

from typing import List
import heapq

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

Explanation:

We first sort the trips based on their pickup location using the key parameter of the sort method.

We initialize an empty list drivers that will store the drivers and their information. We then iterate through each trip in the trips list.

Inside the loop, we use a while loop to check if there exists a driver whose dropoff location is less than or equal to the pickup location of the current trip. If such a driver exists, then we pop the driver with the smallest dropoff location from the drivers list, and add their capacity back to the available seats.

We then check if the capacity is less than the number of passengers for the current trip. If yes, then we cannot find a suitable driver for the trip, and we return False.

Otherwise, we update the available seats in the car, by subtracting the number of passengers for the current trip. We also add the driver to the priority queue based on their dropoff location. We use a heap for the priority queue, and store a tuple of the driver's dropoff location and their car's capacity.

Finally, if we are able to assign all trips, we return True.

Conclusion:

In this problem, we learned how to use a sorting and greedy approach to solve the Carpooling problem. We also learned how to use a priority queue to efficiently find drivers whose dropoff location is less than or equal to the pickup location of a trip. The time complexity of the solution is O(NlogN), and the space complexity is O(N).

1