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 boolean carPooling(int[][] trips, int capacity) {
3 int[] passengerChanges = new int[1001];
4
5 for (int[] trip : trips) {
6 passengerChanges[trip[1]] += trip[0];
7 passengerChanges[trip[2]] -= trip[0];
8 }
9
10 int currentPassengers = 0;
11 for (int change : passengerChanges) {
12 currentPassengers += change;
13 if (currentPassengers > capacity) return false;
14 }
15
16 return true;
17 }
18}The function maintains a difference array and iteratively processes trip information, updating passenger values at their respective journey start and end points. The integrity of capacity limits is validated in a secondary loop.
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).
1def carPooling(trips, capacity):
2 events = []
3 for num_passengers, start, end in trips:
4 events.append((start, num_passengers))
5 events.append((end, -num_passengers))
6
7 events.sort()
8
9 current_passengers = 0
10 for _, change in events:
11 current_passengers += change
12 if current_passengers > capacity:
13 return False
14
15 return TrueEvents are articulated for pick-up and drop-off, indexed and sorted by location metrics. Processing concurrently evaluates car load limits.