We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Car Pooling

Number: 1184

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, Apple, Microsoft, Bloomberg, Lyft

Problem Description

Given a car with a limited seating capacity and an array of trips (each specifying the number of passengers to pick up, the start location, and the drop-off location), determine if the car can pick up and drop off all passengers without exceeding its capacity at any point along its journey eastward.

Key Insights

  • Use a sweep-line algorithm by converting each trip into two events: one for picking up passengers (adding to the load) and one for dropping them off (subtracting from the load).
  • Sort the events by location. For events occurring at the same location, process drop-offs before pick-ups to free up capacity.
  • At each event point, update the current passenger count and verify it does not exceed the car’s capacity.
  • This simulation technique efficiently handles overlapping intervals with a difference array concept.

Space and Time Complexity

Time Complexity: O(N log N) due to sorting the events, where N is the number of trips. Space Complexity: O(N) for storing the events.

Solution

The idea is to transform each trip into two events. For each trip:

  1. Create an event at the 'from' location to add passengers.
  2. Create an event at the 'to' location to subtract passengers. Sort these events by the location value. When events coincide at the same location, process the drop-off events (negative changes) before the pick-up events (positive changes) to ensure capacity is freed before being assigned. Then, iterate over the sorted events, update the cumulative number of passengers, and check against the available capacity. If at any point the current passenger count exceeds the capacity, return false. If the entire journey is simulated without breaching capacity, return true.

Code Solutions

# Python solution with detailed comments

def carPooling(trips, capacity):
    # events will store tuples (location, change_in_passengers)
    events = []
    
    # Create events for each trip: pickup event (+num_passengers) and drop-off event (-num_passengers)
    for num_passengers, start, end in trips:
        events.append((start, num_passengers))   # When passengers get on
        events.append((end, -num_passengers))      # When passengers get off

    # Sort events by location,
    # and in case of ties, process drop-offs (-num_passengers) before pick-ups (+num_passengers)
    events.sort(key=lambda x: (x[0], x[1]))
    
    current_passengers = 0
    
    # Process each event in order of location
    for location, change in events:
        current_passengers += change
        # If at any point, the number of passengers exceeds capacity, return False
        if current_passengers > capacity:
            return False
            
    # If we've processed all events without exceeding capacity, return True
    return True

# Example usage:
print(carPooling([[2,1,5],[3,3,7]], 4))  # Expected output: False
print(carPooling([[2,1,5],[3,3,7]], 5))  # Expected output: True
← Back to All Questions