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.
1public class Solution {
2 public bool CarPooling(int[][] trips, int capacity) {
3 int[] passengerChanges = new int[1001];
4
5 foreach (var trip in trips) {
6 passengerChanges[trip[1]] += trip[0];
7 passengerChanges[trip[2]] -= trip[0];
8 }
9
10 int currentPassengers = 0;
11 foreach (var change in passengerChanges) {
12 currentPassengers += change;
13 if (currentPassengers > capacity) return false;
14 }
15
16 return true;
17 }
18}Leverages a passengerChanges array to track rising and falling passenger metrics according to trip events, verifying that these values never surpass 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).
1#include <stdbool.h>
2#include <stdlib.h>
3
4typedef struct {
5 int time;
6 int passengers;
7} Event;
8
9int cmpEvent(const void* a, const void* b) {
10 return ((Event*)a)->time - ((Event*)b)->time;
11}
12
13bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity) {
14 Event events[2 * tripsSize];
15 int index = 0;
16
17 for(int i = 0; i < tripsSize; i++) {
18 events[index++] = (Event){trips[i][1], trips[i][0]};
19 events[index++] = (Event){trips[i][2], -trips[i][0]};
20 }
21
22 qsort(events, 2 * tripsSize, sizeof(Event), cmpEvent);
23
24 int currentPassengers = 0;
25 for(int i = 0; i < 2 * tripsSize; i++) {
26 currentPassengers += events[i].passengers;
27 if(currentPassengers > capacity) {
28 return false;
29 }
30 }
31
32 return true;
33}We build an array of events, each indicating a change in passenger count, either a pick-up or drop-off, and sort events by time. As we process the events, we update a counter and ensure it never exceeds capacity.