Approach 1: Solving without using given constraints
This is a general greedy approach which does not use the given constraints of the problem. We first sort the trips by their starting position (trip[1]) and use a min-heap to keep track of trips which are going to end. Note that a min heap was chosen so can free up the capacity as soon as the trip ends (i.e., so that we always have ending positions in sorted order). For each trip:
- Until start position of trip (trip[1]) >= ending positions of trips in heap, pop element from heap and do capacity += no. of people who left.
- If capacity < no. of people who want to enter (trip[0]), return false.
- Else, push to priority queue and do capacity -= no. of people.
Code:
bool carPooling(vector<vector<int>>& trips, int capacity) {
sort(trips.begin(), trips.end(), [](vector<int> v1, vector<int>v2) {
if (v1[1]<v2[1])
return true;
return false;
});
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
for (vector<int> v : trips) {
while (!pq.empty() && v[1]>=pq.top().first) {
capacity+=pq.top().second;
pq.pop();
}
if (capacity<v[0])
return false;
capacity -= v[0];
pq.push({v[2], v[0]});
}
return true;
}
Time complexity: O(nlogn)
Approach 2: Using given constraints
We can leverage the given constraints of the question and solve it in linear time (or you can say constant time as trips.length <= 1000). The approach is pretty straightforward (given by @votrubac): Since we only have 1,001 stops, we can just figure out how many people get it and out in each location. Process all trips, adding passenger count to the start location, and removing it from the end location. After processing all trips, a positive value for the specific location tells that we are getting more passengers; negative - more empty seats. Finally, scan all stops and check if we ever exceed our vehicle capacity.
bool carPooling(vector<vector<int>>& trips, int capacity) {
int arr[10001];
memset(arr, 0, sizeof arr);
for (auto t : trips) arr[t[1]] += t[0], arr[t[2]] -= t[0];
for (int i=0; capacity>=0 && i<10001; i++)
capacity -= arr[i];
return capacity>=0;
}
Runtime: O(n), where n is the number of trips (given <= 1000)
Memory: O(m), where m is the number of stops (given <= 1000)