Check carpool trip feasibility

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.

Check Carpool Trip Feasibility

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

Example 1

Input: ([[2, 1, 5], [3, 3, 7]], 4)
Output: False

Explanation: Trips overlap on [3,5]: occupancy reaches 2+3=5 > 4, so the carpool fails.

Example 2

Input: ([[2, 1, 5], [3, 3, 7]], 5)
Output: True

Explanation: Same overlap peaks at exactly 5 = C, which is allowed.

Hints

1. Turn each trip into two events: a pickup (+passengers) at start and a drop-off (-passengers) at end. Sort all events by coordinate.
2. Sweep left to right accumulating a running occupancy. If it ever exceeds C, return False.
3. 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.