Priority Task Executor
Design TaskExecutor:
addTask(taskId, priority, timestamp) executeTask() // runs one task and returns its id, or null when nothing is left
executeTask picks the entry with the highest priority; among equals, the earliest timestamp; among those, the one added first. The same task may be added several times with different priorities or timestamps. A task runs at most once: once executed, every entry for it is ignored, including entries added later.
add("a", 1, 1) · add("a", 9, 2) · add("b", 5, 3)
executeTask() -> "a" executeTask() -> "b" executeTask() -> nullHints
Hint 1
A heap ordered by (−priority, timestamp, insertion sequence) gives the next entry in O(log n). Do not try to remove a task's other entries when it runs.
Hint 2
Lazy deletion: keep a set of executed task ids, and when popping, discard entries whose task has already run until a live one appears.