Buffered Priority Processor
Snap's backend infrastructure handles a diverse array of user requests, ranging from real-time message delivery to background data processing. Efficiently managing these varied tasks on shared processing units is critical for maintaining system responsiveness and optimizing resource utilization. This problem simulates a core aspect of such a system: processing a stream of requests with distinct priorities and specific cooldown requirements on a single processing unit.
Implement a function that simulates a single-core processor managing a stream of incoming requests. The processor must adhere to specific priority rules and a cooldown mechanism for high-priority tasks. Your function should return the order in which requests are completed and their respective finish times.
Function Signature:
function processRequests(requests: Request[], cooldownPeriod: number): Result[];
Input:
requests: An array of Request objects, where each Request is a tuple [id: number, arrivalTime: number, processingTime: number, priority: 'NORMAL' | 'HIGH'].
id: A unique identifier for the request (positive integer).arrivalTime: The time (non-negative integer) at which the request becomes available for processing.processingTime: The duration (positive integer) required to process this request.priority: The priority level, either 'NORMAL' or 'HIGH'.cooldownPeriod: A non-negative integer representing the duration after a HIGH priority task finishes, during which another HIGH priority task cannot start. NORMAL priority tasks can still be processed during this cooldown.Output:
Result tuples [id: number, finishTime: number]. Each tuple represents a completed request, ordered by its finishTime. If two requests finish at the same time, their relative order in the output should match their processing start order.requests array is guaranteed to be sorted by arrivalTime in ascending order. If two requests have the same arrivalTime, their relative order in the input array should be maintained (i.e., the one appearing first is considered to have 'arrived' first).HIGH priority tasks are in cooldown and no NORMAL tasks are pending), the processor remains idle until a task becomes available.HIGH priority tasks are always preferred over NORMAL priority tasks, provided the HIGH priority cooldown is not active.arrivalTime) should be processed first. If arrivalTime is also the same, use the order from the input requests array (which implies using their id as a tie-breaker if ids are sequential).0.Examples
Example 1
Input:
requests = [[1, 0, 3, 'NORMAL'], [2, 1, 2, 'HIGH']], cooldownPeriod = 0
Output:
[[1, 3], [2, 5]]
Note:
Time 0: Request 1 (NORMAL) arrives. Processor starts R1. Time 1: Request 2 (HIGH) arrives. Time 3: Request 1 finishes. Processor free. R2 is available. Processor starts R2. Time 5: Request 2 finishes.
Example 2
Input:
requests = [[1, 0, 2, 'HIGH'], [2, 1, 1, 'NORMAL'], [3, 2, 3, 'HIGH']], cooldownPeriod = 2
Output:
[[1, 2], [2, 3], [3, 7]]
Note:
Time 0: Request 1 (HIGH) arrives. Processor starts R1. Time 1: Request 2 (NORMAL) arrives. Time 2: Request 1 finishes. Cooldown for HIGH starts (ends at 2+2=4). Processor free. R2 is available. Processor starts R2. Time 2: Request 3 (HIGH) arrives. Time 3: Request 2 finishes. Processor free. R3 is available but HIGH cooldown is active (ends at 4). No NORMAL tasks. Processor idles. Time 4: Cooldown ends. Processor free. R3 is available. Processor starts R3. Time 7: Request 3 finishes.
Example 3
Input:
requests = [[10, 0, 1, 'NORMAL'], [20, 0, 1, 'NORMAL'], [30, 2, 2, 'HIGH']], cooldownPeriod = 1
Output:
[[10, 1], [20, 2], [30, 4]]
Note:
Time 0: R10, R20 (both NORMAL) arrive. R10 processed first (earlier in input). Time 0-1: Process R10. Time 1: R10 finishes. Processor free. R20 available. Process R20. Time 1-2: Process R20. Time 2: R20 finishes. Processor free. R30 (HIGH) arrives. Cooldown for HIGH is not active. Process R30. Time 2-4: Process R30. Time 4: R30 finishes.
Constraints
1 <= requests.length <= 10^50 <= arrivalTime < 10^91 <= processingTime <= 10^4ids are unique positive integers.priority is either 'NORMAL' or 'HIGH'.0 <= cooldownPeriod <= 10^4requests array is sorted by arrivalTime.0.HIGH and NORMAL priority queues.Loading editor...