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 <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 bool carPooling(std::vector<std::vector<int>>& trips, int capacity) {
7 int passengerChanges[1001] = {0};
8
9 for(const auto& trip : trips) {
10 passengerChanges[trip[1]] += trip[0];
11 passengerChanges[trip[2]] -= trip[0];
12 }
13
14 int currentPassengers = 0;
15 for(int i = 0; i < 1001; ++i) {
16 currentPassengers += passengerChanges[i];
17 if (currentPassengers > capacity) return false;
18 }
19
20 return true;
21 }
22};Similar to the C implementation, we use a difference array for passenger changes. The core logic processes trips to adjust the difference array and then checks cumulative passengers against 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).
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public bool CarPooling(int[][] trips, int capacity) {
6 List<int[]> events = new List<int[]>();
7
8 foreach (var trip in trips) {
9 events.Add(new int[]{trip[1], trip[0]}); // pickup
10 events.Add(new int[]{trip[2], -trip[0]}); // drop-off
11 }
12
13 events.Sort((a, b) => a[0] - b[0]);
14
15 int currentPassengers = 0;
16 foreach (var ev in events) {
17 currentPassengers += ev[1];
18 if (currentPassengers > capacity) return false;
19 }
20
21 return true;
22 }
23}Carrying each trip as event-based modifications, we sort and manage updates correspondingly to ensure no overcapacity occurs.