Priority Task Scheduler

Priority Task Scheduler

Design the dispatch core of a job runner: tasks arrive with a priority and a ready-time, and each poll must hand back the highest-priority task that is ready to run right now.

Requirements

• schedule only registers a task; it never runs one. A task stays pending until a next call picks it.
• next(ts) is the dispatcher: consider only pending tasks with readyTs ≤ ts, choose the highest priority, break ties by smaller taskId, then remove that task and return its id.
• If no pending task is ready at ts, next returns -1 (and removes nothing).
• Time is logical and only moves forward: the ts given to successive next calls is non-decreasing. Never read a real clock and never spawn a thread — model everything single-threaded and deterministically.
• A larger priority number means more important. Task ids need not be contiguous.

API to implement

Implement the class Scheduler. The I/O driver is already written in the starter code — it parses the command script below and calls your methods. You only implement the class.

| Command | Returns | Behavior | |---|---|---| | schedule <taskId> <priority> <readyTs> | — | Register a task with id taskId and the given priority, eligible to run once time reaches readyTs. | | next <ts> | int | Among all scheduled-but-not-yet-run tasks whose readyTs ≤ ts, remove and return the one with the highest priority (ties broken by smaller taskId). Return -1 if none is ready. The ts values passed across successive next calls are non-decreasing. |

Input format

The first line contains Q, the number of operations. Each of the next Q lines is one command as listed above. String arguments contain no spaces.

Output format

For each command with a non-void return, print its result on its own line, in order. The driver does this for you — your methods just return values.

This is a design problem: the hidden tests exercise edge cases and interaction sequences, not performance tricks. Model the state cleanly and the tests will pass.

7
schedule 1 5 0
schedule 2 8 0
schedule 3 8 0
next 0
next 0
next 0
next 0

2
3
1
-1

6
schedule 10 3 5
schedule 20 7 10
next 4
next 5
next 9
next 10

-1
10
-1
20