car pooling

XXX. Car Pooling

Sweep Line

Sorting

Problem Statement:

Given a list of trips with [numPassengers, start, end] and a capacity, determine if it's possible to complete all trips without exceeding the car's capacity.

• Each trip has pickup and dropoff locations
• Multiple trips can overlap
• Cannot exceed capacity at any point

Implementation:

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // Sort trips by start location
        Arrays.sort(trips, (a,b) -> a[1] - b[1]);
        
        // Create events for pickups and dropoffs
        List events = new ArrayList<>();
        for (int[] trip : trips) {
            events.add(new Event(trip[0], trip[1], true));   // Pickup event
            events.add(new Event(trip[0], trip[2], false));  // Dropoff event
        }
        
        // Sort events by location
        Collections.sort(events, (a,b) -> a.location - b.location);
        
        // Process events in order
        int numPassengers = 0;
        for (Event event : events) {
            if (event.pickup)                                // Add passengers
                numPassengers += event.passengers;
            else                                            // Remove passengers
                numPassengers -= event.passengers;
                
            if (numPassengers > capacity) return false;     // Check capacity
        }
        
        return true;
    }
    
    // Helper class to represent pickup/dropoff events
    class Event {
        int passengers;
        int location;
        boolean pickup;
        
        public Event(int passengers, int location, boolean pickup) {
            this.passengers = passengers;
            this.location = location;
            this.pickup = pickup;
        }
    }
}

Complexity:

Time Complexity: O(n log n) for sorting events
Space Complexity: O(n) for events list

Key Points:

• **Event-Based Approach**:
  • Split each trip into pickup/dropoff events
  • Sort events by location
  • Track running passenger count
• **Passenger Tracking**:
  • Add passengers at pickup
  • Remove passengers at dropoff
  • Check capacity after each change

Example:

For trips = [[2,1,5],[3,3,7]], capacity = 4:

• Events after sorting:
  • Location 1: +2 passengers
  • Location 3: +3 passengers (total 5 > 4)
  • Return false

Implementation Notes:

• **Event Processing**:
  • Sort to process in location order
  • Handle pickups before dropoffs at same location
  • Early exit on capacity violation
• **Edge Cases**:
  • Multiple events at same location
  • Zero passenger trips
  • Single passenger trip