[[2,1,5],[3,3,7]]
, capacity = 4
Output: false[[2,1,5],[3,3,7]]
, capacity = 5
Output: truet => 1 2 3 4 5 6 7 8
trip#1 2 2 2 2 2
trip#2 3 3 3 3 3
total# 2 2 5 5 5 3 3 0
- - exceeded - - -
A common approach that comes to mind is to track num of passengers at each point in pos.
There are two operations involved, filling and emptying the car. To better track operations, it is better if we sort acc to start pos of the trip and iterate. We can empty at same pos, if prev trip passengers’ pos expires before or at the current start.
def carpool(trips, capacity) :
trips = sorted(trips, key = lambda x : x[1]) # sort acc to end pos
cap_used = 0
for num, start, end in trips :
cap_used += num
# -- still thinking next step --
Here we are using custom key, ele at idx1 in the trip
To remove passengers from expired trip we need to store the trips in a structure. Such that
we can easily check if any trip with end pos less than start is already present.
We use a priority queue acc to end pos, so that it always gives us the last active trip that ends.
If the trip expires at or before the current start, we can immediately free up the space
def carpool(trips , capacity):
trips = sorted(trips, key = lambda x: x[1]) # sort by start pos
pq = PriorityQueue() # end pos, num
cap_used = 0
for num, start, end in trips :
# free up space from the earlier trip; if possible
while pq.queue and pq.queue[0][0] <= start :
cap_used -= pq.get()[1]
#include the cur trip for now :
cap_used += num #determnine later if it frees up space eventually
pq.put((end, num))
if cap_used > capacity :
return False
return True
One more trick that comes often in the problems involving allocation uses the concept of delta. Delta signifies the change that occurs at some given point
def carpool(trips, capacity) :
deltas = []
for n, start, end in trips:
deltas.append((start, n))
deltas.append((end, -n))
deltas.sort()
We need to track positions from left to right, its sensible to sort these deltas. It makes tracking capacity used easier to track.
Iterate over these deltas and keep operating on the capacity used. Since deltas are positive and negative, adding them up to certain point will yield the capacity used at that point. This includes the contribution form positions before it as we are going left to right.
cap_used = 0
for loc in lst:
cap_used += loc[1]
if cap_used > capacity:
return False
return True
Finally
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
lst = []
for n, start, end in trips:
lst.append((start, n))
lst.append((end, -n))
lst.sort()
pas = 0
for loc in lst:
pas += loc[1]
if pas > capacity:
return False
return True
Coming soon...