Incident Priority Pager
An incident pager processes a stream of incidents, each with a severity (1 = highest). The on-call engineer can handle one incident at a time. New incidents may arrive while one is being handled. Determine the order in which incidents are handled if the engineer always picks the highest-severity (lowest-numbered) incident currently in the queue when they become free.
Problem
Given a list of events sorted by arrival timestamp, each (arrival_time, incident_id, severity, handle_time), produce the order (by incident_id) in which the engineer finishes handling them. Tie-break by earliest arrival_time. The engineer is idle until the first event; whenever they finish, they immediately pick the pending incident with the lowest severity (highest priority); if no incident is pending, they idle until the next arrival.
Input
An integer n (1 ≤ n ≤ 10^5) and n records (arrival, id, severity, handle_time) with 0 ≤ arrival ≤ 10^9, 1 ≤ severity ≤ 10, 1 ≤ handle_time ≤ 10^6. Records arrive sorted by arrival.
Output
A list of n incident IDs in the order they finish processing.
Constraints
- 1 ≤ n ≤ 100,000
- Severity 1 = highest priority. 10 = lowest.
- Ties by arrival_time; further ties by incident_id ascending
- Incidents that arrive while the engineer is busy queue up
Examples
Example 1
Input
events = [(0, 1, 2, 5), (1, 2, 1, 3), (2, 3, 3, 1)]
Output
[1, 2, 3]
At t=0, engineer picks incident 1 (only one queued), finishes at t=5. During [0,5], incidents 2 and 3 arrive. At t=5, engineer picks the highest-priority pending: severity 1 (incident 2), finishes at t=8. Then incident 3 at t=9. Order: 1, 2, 3.