Compute peak busy dashers with overlaps

You are given delivery logs as (dasherId, startTime, endTime) with integer times, where endTime is exclusive. A single dasher may accept multiple orders that overlap in time. a) Compute the maximum number of busy dashers at any moment, counting each dasher at most once at any given time even if they hold multiple overlapping orders. b) Design and implement an O(n log n) sweep-line algorithm: describe how you create events, how you deduplicate multiple simultaneous starts for the same dasher, and how you handle ties so that an end at time t is processed before a start at time t. c) If your event tuples include dasherId, explain the pitfall of sorting by (dasherId, time, delta) and provide a correct key/comparator (e.g., (time, delta, dasherId) with delta ordered so -1 comes before + 1). d) How would your approach change if dashers could not take overlapping orders (i.e., you’re asked for the peak number of concurrent orders instead)? Analyze time and space complexity.

Part 1: Peak Busy Dashers with Overlapping Orders

You are given delivery logs where each log is [dasherId, startTime, endTime]. Times are integers, and endTime is exclusive. A dasher may hold multiple overlapping or back-to-back orders, but at any single moment that dasher should count at most once. Return the maximum number of distinct dashers that are busy at the same time.

Constraints

• 0 <= len(logs) <= 200000
• 0 <= dasherId <= 10^9
• 0 <= startTime < endTime <= 10^9
• endTime is exclusive

Examples

Example 1

Input: [[1, 1, 5], [1, 2, 6], [2, 4, 7]]
Output: 2

Explanation: Dasher 1 is busy continuously from 1 to 6 after merging its overlapping orders. Dasher 2 overlaps from 4 to 6, so the peak is 2.

Example 2

Input: [[1, 1, 3], [2, 3, 5]]
Output: 1

Explanation: Because endTime is exclusive, the first order ends before the second begins at time 3.

Hints

1. First combine each dasher's intervals so overlapping or touching intervals become one busy block.
2. After merging per dasher, the problem becomes a standard interval overlap sweep.

Part 2: Sweep-Line Busy Dashers in O(n log n)

You are given delivery logs where each log is [dasherId, startTime, endTime]. Times are integers and endTime is exclusive. Implement an O(n log n) sweep-line algorithm that computes the maximum number of busy dashers. Create start and end events for every order, process all events in chronological order, and when times tie, process end events before start events. A dasher may have multiple overlapping orders, so use per-dasher active-order counts: a dasher should increase the busy count only when its active count changes from 0 to 1, and decrease it only when its active count changes from 1 to 0.

Constraints

• 0 <= len(logs) <= 200000
• 0 <= dasherId <= 10^9
• 0 <= startTime < endTime <= 10^9
• You should target O(n log n) time

Examples

Example 1

Input: [[1, 1, 4], [1, 1, 3], [2, 2, 5]]
Output: 2

Explanation: Dasher 1 starts two orders at time 1 but still counts as only one busy dasher. Dasher 2 overlaps later, so the peak is 2.

Example 2

Input: [[1, 1, 3], [1, 3, 5], [2, 3, 4]]
Output: 2

Explanation: At time 3, dasher 1's first order ends before its second begins. Dasher 2 also starts at 3, so the peak becomes 2.

Hints

1. Sort events by (time, delta, dasherId) if you encode end as -1 and start as +1.
2. Multiple starts for the same dasher at the same time should not raise the busy count more than once; track active orders per dasher.

Part 3: Correctly Sort Sweep-Line Events

Each event is represented as [dasherId, time, delta], where delta is -1 for an end event and 1 for a start event. Sorting by (dasherId, time, delta) is incorrect because it groups events by dasher instead of processing the global timeline. Write a function that returns the events in the correct sweep-line order: sort by time ascending, then delta ascending so -1 comes before 1, then dasherId ascending.

Constraints

• 0 <= len(events) <= 200000
• 0 <= dasherId <= 10^9
• 0 <= time <= 10^9
• delta is either -1 or 1

Examples

Example 1

Input: [[2, 5, 1], [1, 3, 1], [1, 5, -1]]
Output: [[1, 3, 1], [1, 5, -1], [2, 5, 1]]

Explanation: Time 3 comes before time 5. At time 5, the end event comes before the start event.

Example 2

Input: [[2, 4, 1], [1, 4, -1], [3, 4, 1]]
Output: [[1, 4, -1], [2, 4, 1], [3, 4, 1]]

Explanation: All events share the same time, so delta decides first and dasherId breaks the remaining tie.

Hints

1. The sweep-line must move through time globally, so time has to be the first sort key.
2. When two events share the same time, an end event should come before a start event because endTime is exclusive.

Part 4: Peak Concurrent Orders When Dashers Cannot Overlap Orders

You are given delivery logs where each log is [dasherId, startTime, endTime]. Times are integers and endTime is exclusive. In this version, dashers cannot take overlapping orders. That means each active order belongs to a different dasher, so the task reduces to finding the maximum number of concurrent orders. Return the peak number of simultaneously active orders.

Constraints

• 0 <= len(logs) <= 200000
• 0 <= dasherId <= 10^9
• 0 <= startTime < endTime <= 10^9
• Orders for the same dasher do not overlap

Examples

Example 1

Input: [[1, 1, 4], [2, 2, 5], [3, 3, 6]]
Output: 3

Explanation: All three orders overlap between times 3 and 4.

Example 2

Input: [[1, 1, 3], [2, 3, 5], [3, 5, 7]]
Output: 1

Explanation: Because endTime is exclusive, these intervals only touch and never overlap.

Hints

1. You no longer need per-dasher active counts, because each order can be counted directly.
2. Use the standard interval sweep: add +1 at starts and -1 at ends, with ends processed before starts at the same time.