Pooled Rideshare Earnings With Concurrent Rides and Surge

A rideshare driver works a pooled shift, ferrying overlapping sets of riders along one continuous route, and gets compensated minute by minute according to how full the car is. For any given minute, pay for that minute equals base_rate multiplied by however many riders happen to be riding along right then.

Layered on top of that are surge windows: stretches of time where whatever a minute would normally pay gets doubled, on account of high demand.

Given the base rate, the rider pickup/dropoff log, and the surge windows, work out the driver's total take-home for the shift.

Function Signature

def driver_earnings(base_rate: int, rides: list[list[int]], surge_windows: list[list[int]]) -> int:

Each rides[i] = [pickup, dropoff] places rider i in the car from minute pickup through (but excluding) minute dropoff. Each surge_windows[j] = [start, end] is active from start through (but excluding) end. Every timestamp is a whole minute on one common clock, and earnings are expressed in cents.

Rules

• Rider i occupies the car during exactly the minutes m satisfying pickup <= m < dropoff — the dropoff minute is excluded.
• A surge window is in effect for exactly the minutes m satisfying start <= m < end.
• Define occupancy(m) as the rider headcount during minute m. Pay for that minute is base_rate * occupancy(m), doubled to 2 * base_rate * occupancy(m) if the minute falls inside an active surge window. An empty car earns nothing for that minute, surge or not.
• Sum pay across every minute to get the answer; an empty rides list yields 0.
• Rides are free to overlap in arbitrary patterns, and a ride's boundaries can land anywhere relative to a surge window, including mid-window.

Constraints

• 1 <= base_rate <= 500
• 0 <= len(rides) <= 10^5, with every ride satisfying 0 <= pickup < dropoff <= 10^6
• 0 <= len(surge_windows) <= 10^5, with every window satisfying 0 <= start < end <= 10^6
• Surge windows never overlap one another, though one is allowed to end exactly where the next begins. Input order for both lists is arbitrary.
• The final total can climb to roughly 2 * 10^14. A 32-bit counter can't hold that, so carry the running sum in 64-bit arithmetic; it still fits comfortably under 2^53.

Two worked cases follow.

Examples

Example 1

Input:  base_rate = 12, rides = [[5, 45], [20, 60]], surge_windows = []
Output: 960

Minutes 5-19 have 1 rider (15 minutes x 12 = 180), minutes 20-44 have 2 riders (25 minutes x 24 = 600), minutes 45-59 have 1 rider again (15 minutes x 12 = 180). Total: 180 + 600 + 180 = 960.

Example 2

Input:  base_rate = 12, rides = [[5, 45], [20, 60]], surge_windows = [[30, 40]]
Output: 1200

Same rides as Example 1, but minutes 30-39 fall inside the surge window and inside the 2-rider overlap, so those 10 minutes pay 2 * 12 * 2 = 48 each instead of 24 - an extra 10 * 24 = 240 on top of Example 1's total: 960 + 240 = 1200.