Calculate Courier Earnings

Design a function to calculate total courier pay from a set of delivery orders.

Assume time is represented as integer minutes, and intervals are half-open: an order active from minute start to minute end contributes on [start, end).

Base version

Each order has:

• accepted_at
• delivered_at

There is a global rate paid per minute.

For any minute in which an order is active, that order earns rate * k, where k is the number of orders active in that same minute. In other words, if k orders overlap during a minute, the total pay contributed by that minute is k * k * rate.

Implement a function that returns the total pay across all orders.

The interviewer may ask you to define reasonable input/output structures yourself, explain your chosen data structures, analyze time and space complexity, and write meaningful test cases.

Follow-up 1

Now each order may also include:

• arrived_at
• picked_up_at

The interval [arrived_at, picked_up_at) is store-wait time. A store-wait minute is paid only for that order itself:

• it must not increase the multiplier for any other order
• other orders must not increase its multiplier

Update the design to support this rule.

Follow-up 2

During configurable peak-hour intervals, the per-minute rate is doubled.

Explain how you would extend your solution to support this efficiently.

Part 1: Calculate total courier pay with overlapping delivery intervals

You are given a base pay rate per minute and a list of delivery orders. Each order is active on the half-open interval [accepted_at, delivered_at). If k orders are active during the same minute, then each of those k orders earns rate * k for that minute, so the total pay added by that minute is k * k * rate. Return the total pay across all orders.

Constraints

• 0 <= len(orders) <= 200000
• 0 <= rate <= 10^6
• 0 <= accepted_at <= delivered_at <= 10^9
• Orders use half-open intervals: [start, end)
• The final answer fits in a signed 64-bit integer

Examples

Example 1

Input: (5, [])
Output: 0

Explanation: No orders means no pay.

Example 2

Input: (10, [[0, 3]])
Output: 30

Explanation: One order is active for 3 minutes, so pay is 3 * 1^2 * 10 = 30.

Hints

1. A minute-by-minute simulation is too slow when timestamps are large.
2. The number of active orders changes only at start and end times, so process intervals between sorted event times.

Part 2: Support store-wait intervals that do not affect overlap multipliers

Each order is given as [accepted_at, arrived_at, picked_up_at, delivered_at], with accepted_at <= arrived_at <= picked_up_at <= delivered_at. The full order runs on [accepted_at, delivered_at), but the sub-interval [arrived_at, picked_up_at) is store-wait time. A store-wait minute is paid only for that order itself: it does not increase any other order's overlap multiplier, and other orders do not increase its multiplier. Minutes outside store-wait behave like normal delivery minutes and interact with other normal delivery minutes using the same k * k * rate rule. Return the total pay.

Constraints

• 0 <= len(orders) <= 200000
• 0 <= rate <= 10^6
• 0 <= accepted_at <= arrived_at <= picked_up_at <= delivered_at <= 10^9
• All intervals are half-open
• The final answer fits in a signed 64-bit integer

Examples

Example 1

Input: (5, [])
Output: 0

Explanation: No orders means no pay.

Example 2

Input: (10, [[0, 2, 4, 6]])
Output: 60

Explanation: Normal segments are [0,2) and [4,6), and wait is [2,4). All are paid at rate 10 with no overlaps, for 6 total minutes.

Hints

1. Split each order into up to three pieces: pre-wait, wait, and post-wait.
2. Store-wait pay is isolated, so you can count its contribution separately from the overlapping normal segments.

Part 3: Support doubled per-minute rates during configurable peak-hour intervals

Extend the previous rules. Each order is [accepted_at, arrived_at, picked_up_at, delivered_at], where [arrived_at, picked_up_at) is isolated store-wait time. You are also given peak-hour intervals [start, end). During any minute covered by at least one peak interval, the per-minute rate is doubled. If peak intervals overlap, the rate is still only doubled once, not repeatedly. Return the total pay efficiently.

Constraints

• 0 <= len(orders) <= 200000
• 0 <= len(peak_intervals) <= 200000
• 0 <= rate <= 10^6
• 0 <= accepted_at <= arrived_at <= picked_up_at <= delivered_at <= 10^9
• 0 <= peak_start <= peak_end <= 10^9
• All intervals are half-open
• If multiple peak intervals overlap, the rate is doubled once for covered minutes
• The final answer fits in a signed 64-bit integer

Examples

Example 1

Input: (5, [], [[0, 10]])
Output: 0

Explanation: Peak hours do not matter if there are no orders.

Example 2

Input: (10, [[0, 2, 4, 6]], [])
Output: 60

Explanation: With no peak intervals, this matches the previous problem.

Hints

1. Sweep over all times where something changes: a normal segment starts or ends, a wait segment starts or ends, or a peak interval starts or ends.
2. For each constant segment, the pay is segment_length * effective_rate * (normal_active^2 + wait_active).