We can simulate the number of passengers in the car at each kilometer using a difference array. For each trip, increase the passenger count at fromi and decrease it at toi. Then, iterate through this array to calculate the actual number of passengers at each point, checking if it ever exceeds the capacity.
Time Complexity: O(n + m) where n is the number of trips and m is the max distance (1000).
Space Complexity: O(m) for the difference array.
1#include <stdbool.h>
2#include <string.h>
3
4bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity) {
5 int passengerChanges[1001];
6 memset(passengerChanges, 0, sizeof(passengerChanges));
7
8 for(int i = 0; i < tripsSize; i++) {
9 int numPassengers = trips[i][0];
10 int from = trips[i][1];
11 int to = trips[i][2];
12
13 passengerChanges[from] += numPassengers;
14 passengerChanges[to] -= numPassengers;
15 }
16
17 int currentPassengers = 0;
18 for(int i = 0; i < 1001; i++) {
19 currentPassengers += passengerChanges[i];
20 if(currentPassengers > capacity) {
21 return false;
22 }
23 }
24
25 return true;
26}The implementation maintains an array passengerChanges that models changes in the number of passengers at various kilometer points. We iterate over each trip, updating the number of passengers picked up and dropped off. Lastly, we traverse the passengerChanges calculating the current number of passengers and verifying it does not exceed the capacity.
In this approach, we treat each pick-up and drop-off as events. We collect all events, sort them based on location, and then simulate the process of picking up and dropping off passengers by iterating through events in order, checking if it ever exceeds the car's capacity.
Time Complexity: O(n log n), driven by sorting events.
Space Complexity: O(n).
1import java.util.*;
2
3public class Solution {
4 public boolean carPooling(int[][] trips, int capacity) {
5 List<int[]> events = new ArrayList<>();
6
7 for (int[] trip : trips) {
8 events.add(new int[]{trip[1], trip[0]}); // pickup
9 events.add(new int[]{trip[2], -trip[0]}); // drop-off
10 }
11
12 events.sort((a, b) -> a[0] - b[0]);
13
14 int currentPassengers = 0;
15 for (int[] event : events) {
16 currentPassengers += event[1];
17 if (currentPassengers > capacity) return false;
18 }
19
20 return true;
21 }
22}Represented as pick-up and drop-off events, we sort and sequentially evaluate each event in terms of its change to car burdens, returning a boolean determination.