Check carpool trip feasibility
Company: Meta
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of trips where each trip i is (passengers_i, start_i, end_i) with start_i < end_i on a one-dimensional route. A single vehicle with capacity C moves in the increasing direction only; passengers board at start_i and alight at end_i. Implement can_complete_carpool(trips, C) that returns True iff all trips can be completed without exceeding capacity at any point. Use a sweep-line approach with +passengers at start_i and -passengers at end_i; target time/position complexity O(n log n). Discuss edge cases when multiple events share the same coordinate.
Quick Answer: This question evaluates understanding of sweep-line algorithms, interval/event aggregation, and complexity analysis for capacity-constrained scheduling on a one-dimensional route, including handling simultaneous events and edge cases in event ordering.
You are given a list of `trips`, where each trip is `(passengers, start, end)` with `start < end` on a one-dimensional route. A single vehicle with capacity `C` moves only in the increasing direction. For each trip, `passengers` board at position `start` and alight at position `end`.
Implement `can_complete_carpool(trips, C)` that returns `True` if and only if every trip can be completed without the number of passengers on board exceeding `C` at any point along the route, and `False` otherwise.
Use a sweep-line approach: emit a `+passengers` event at each `start` and a `-passengers` event at each `end`, sort the events by coordinate, and scan left to right tracking the running occupancy. Target complexity is O(n log n) time.
Edge case to handle carefully: when a drop-off and a pickup share the same coordinate, the passenger alighting at that position frees their seat *before* the boarding passenger takes one. Process the negative (alight) event before the positive (board) event at any tied coordinate.
Constraints
- 0 <= len(trips) <= 10^5
- 1 <= passengers_i <= 10^4
- 0 <= start_i < end_i <= 10^9
- 0 <= C <= 10^9
Examples
Input: ([[2, 1, 5], [3, 3, 7]], 4)
Expected Output: False
Explanation: Trips overlap on [3,5]: occupancy reaches 2+3=5 > 4, so the carpool fails.
Input: ([[2, 1, 5], [3, 3, 7]], 5)
Expected Output: True
Explanation: Same overlap peaks at exactly 5 = C, which is allowed.
Hints
- Turn each trip into two events: a pickup (+passengers) at start and a drop-off (-passengers) at end. Sort all events by coordinate.
- Sweep left to right accumulating a running occupancy. If it ever exceeds C, return False.
- When a drop-off and a pickup land on the same coordinate, process the drop-off first (sort negative deltas before positive ones at equal coordinates) so a freed seat can be immediately reused.