Car Pooling

Problem Statement

In the given problem, a car with a specified number of empty seats (capacity) is tasked with transporting passengers Eastward without the option of turning West. Each trip, characterized by a number of passengers (numPassengersi), a pickup location (fromi), and drop off location (toi), is detailed within an array trips. Each element in this trips array represents a single journey, where the locations (fromi and toi) are distances measured in kilometers east from the starting point of the car.

The challenge lies in determining if the car can manage all scheduled trips without exceeding its passenger capacity at any given point in the journey. The objective is to return true if the car can accommodate all passengers for every trip as per their requirements; otherwise, return false.

Examples

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

Constraints

• 1 <= trips.length <= 1000
• trips[i].length == 3
• 1 <= numPassengersi <= 100
• 0 <= fromi < toi <= 1000
• 1 <= capacity <= 105

Approach and Intuition

To solve this problem, we need to track the number of passengers in the vehicle at each point in the journey based on the trips' pickup and drop-off events. Here’s a step-by-step breakdown:

1. First, understand the number of changes in passenger count at each event (pickup or dropoff). This can be done by creating a list or array where each index represents a point (kilometer) in the journey, and the value at each index alters based on passenger events happening at that location.

2. Initialize a list with a length equal to the furthest distance (toi) in trips plus one (to accommodate zero indexing), filled initially with zeros. This array will represent passenger changes at each kilometer of the journey.

3. For each trip in trips, increment the passenger count at the index representing the pickup location (fromi) by the number of passengers (numPassengersi), and decrement it at the index representing one past the drop-off location (toi) as passengers will be leaving the car.

4. Walk through the passenger change array cumulatively to calculate the total number of passengers in the car at each kilometer. This is akin to applying the prefix sum technique where each value in the accumulation array changes based on the net effect of passenger pickups and drop-offs up to that point.

5. During this walk, if at any point the number of passengers in the car exceeds the capacity, immediately return false. If you complete the walk without exceeding the car's capacity, return true.

By applying this approach, we can efficiently determine if the car can manage all the scheduled trips within the given passenger capacity constraints.

Solutions

class Solution {
    public boolean canCarPool(int[][] rides, int maxCapacity) {
        int[] timeStamps = new int[1001];
        for (int[] ride : rides) {
            timeStamps[ride[1]] += ride[0];
            timeStamps[ride[2]] -= ride[0];
        }
        int currentLoad = 0;
        for (int load : timeStamps) {
            currentLoad += load;
            if (currentLoad > maxCapacity) {
                return false;
            }
        }
        return true;
    }
}