Car Pooling Capacity
Problem
A car drives east along a straight road and can never turn back. Each trip is (riders, start, end): that many people board at start and leave at end. Given a seat capacity, decide whether every trip can be served without ever exceeding it. Passengers leaving at a point free their seats before anyone boarding at that same point sits down.
Examples
Input: trips = [(2, 1, 5), (3, 3, 7)], capacity = 4
Output: False
Why: between 3 and 5 both groups are aboard, needing 5 seatsInput: trips = [(2, 1, 5), (3, 5, 7)], capacity = 3
Output: True
Why: the first group leaves at 5 exactly as the second boardsInput: trips = [], capacity = 0
Output: True
Why: edge case, no trips can never overflowHints
0 / 3
The seat count only changes at trip starts and ends, so nothing between those points needs checking.
Turn each trip into two events on the road: a rise in occupancy where it starts, and a fall where it ends.
Sort the events by position and run a running total, checking it after every change. Make a fall sort before a rise at the same position so that the seats are freed first, then compare the total against the capacity.
Solution
This is a sweep line over positions rather than a comparison of intervals. Each trip becomes a +riders event at its start and a -riders event at its end; the running sum after each event is the exact occupancy on that stretch of road. Sorting the pairs directly puts a negative delta before a positive one at the same position, which is precisely the "leave before board" rule. Time is O(n log n) for the sort, space O(n) for the events.
def can_carry(trips, capacity):
events = []
for riders, start, end in trips:
events.append((start, riders)) # board
events.append((end, -riders)) # alight; negative sorts first on ties
events.sort()
onboard = 0
for _, delta in events:
onboard += delta
if onboard > capacity:
return False
return True
print(can_carry([(2, 1, 5), (3, 3, 7)], 4)) # -> False
print(can_carry([(2, 1, 5), (3, 5, 7)], 3)) # -> True
print(can_carry([], 0)) # -> TrueStuck on the idea rather than the code? Meeting Rooms covers it.