Car pool capacity check

Scenario

A ride-sharing van drives along a straight road marked in kilometres. Each booking has a group of passengers who are picked up at one kilometre mark and dropped off at a later one. The van holds a fixed number of passengers.

At a stop, passengers getting off leave before new passengers get on. You get the bookings and the capacity of the van. Find the first kilometre mark at which the van would be over capacity.

Your task

Write first_overload(passengers, pickup, dropoff, capacity).

Booking i has passengers[i] people, picked up at pickup[i] and dropped off at dropoff[i], with pickup[i] < dropoff[i].
The group is on board from pickup[i] up to, but not including, dropoff[i].
Return the smallest kilometre mark at which the number of people on board is more than capacity. Return -1 if that never happens.

Examples

Example 1 (traced)#

text2 lines

Input:  passengers = [2, 1, 3], pickup = [1, 2, 4], dropoff = [5, 4, 8], capacity = 4
Output: 4

Turn each booking into two events: people get on at the pickup mark, and get off at the drop-off mark. Sort the events by mark, with get-off events first at the same mark. Then add up.

Mark	Event	People on board	Over 4?
1	2 get on	2	no
2	1 gets on	3	no
4	1 gets off	2	no
4	3 get on	5	yes: mark 4

The van is over capacity at mark 4.

Example 2#

text2 lines

Input:  passengers = [2, 3], pickup = [1, 5], dropoff = [5, 7], capacity = 3
Output: -1

At mark 5, the first group gets off before the second group gets on. The van never holds more than 3 people.

Example 3#

text2 lines

Input:  passengers = [3], pickup = [1], dropoff = [5], capacity = 2
Output: 1

One group of 3 is already more than the capacity of 2 when it gets on at mark 1.

Constraints

0 ≤ passengers.length = pickup.length = dropoff.length ≤ 100,000 (bookings)
1 ≤ passengers[i] ≤ 100
0 ≤ pickup[i] < dropoff[i] ≤ 1,000,000,000 (kilometre marks)
1 ≤ capacity ≤ 1,000,000

What does n ≤ 10^5 tell you?

Adding up the people on board at every pickup mark, by checking every booking, costs about n × n, which is 10^10 at n = 100,000. Marks go up to 10^9, so an array with one cell for each mark is too big. Sorting the 2n events costs about n log n.

Scenario

At a stop, passengers getting off leave before new passengers get on. You get the bookings and the capacity of the van. Find the first kilometre mark at which the van would be over capacity.

Your task

Write first_overload(passengers, pickup, dropoff, capacity).

Booking i has passengers[i] people, picked up at pickup[i] and dropped off at dropoff[i], with pickup[i] < dropoff[i].
The group is on board from pickup[i] up to, but not including, dropoff[i].
Return the smallest kilometre mark at which the number of people on board is more than capacity. Return -1 if that never happens.

Examples

Example 1 (traced)#

text2 lines

Input:  passengers = [2, 1, 3], pickup = [1, 2, 4], dropoff = [5, 4, 8], capacity = 4
Output: 4

Turn each booking into two events: people get on at the pickup mark, and get off at the drop-off mark. Sort the events by mark, with get-off events first at the same mark. Then add up.

Mark	Event	People on board	Over 4?
1	2 get on	2	no
2	1 gets on	3	no
4	1 gets off	2	no
4	3 get on	5	yes: mark 4

The van is over capacity at mark 4.

Example 2#

text2 lines

Input:  passengers = [2, 3], pickup = [1, 5], dropoff = [5, 7], capacity = 3
Output: -1

At mark 5, the first group gets off before the second group gets on. The van never holds more than 3 people.

Example 3#

text2 lines

Input:  passengers = [3], pickup = [1], dropoff = [5], capacity = 2
Output: 1

One group of 3 is already more than the capacity of 2 when it gets on at mark 1.

Constraints

0 ≤ passengers.length = pickup.length = dropoff.length ≤ 100,000 (bookings)
1 ≤ passengers[i] ≤ 100
0 ≤ pickup[i] < dropoff[i] ≤ 1,000,000,000 (kilometre marks)
1 ≤ capacity ≤ 1,000,000

What does n ≤ 10^5 tell you?