Message queues often support delayed delivery and priorities at the same time. A scheduled message must remain hidden until its availability timestamp, while ready messages compete according to a deterministic priority policy.
Design a DelayedPriorityQueue class:
DelayedPriorityQueue() creates an empty queue.void enqueue(int messageId, int availableAt, int priority) adds a message and records its insertion order.int poll(int timestamp) removes and returns the best eligible message, or -1 when none is ready.
A message is eligible when availableAt <= timestamp. Among eligible messages:
- Greater
priority wins. - If priorities tie, smaller
availableAt wins. - If both tie, the message enqueued earlier wins.
Do not let an ineligible high-priority message block eligible work. Poll timestamps are non-decreasing.
Example 1:
Input:
Output:
Explanation: Nothing is ready at time 4. At time 5, message 3 wins by priority, followed by message 2. Message 1 becomes eligible at time 10.
Example 2:
Input:
Output:
Explanation: Availability and priority tie, so insertion order decides.
Constraints
0 <= availableAt, timestamp <= 10^9-10^9 <= priority <= 10^9- Message IDs are unique within one object.
- Poll timestamps are non-decreasing.
- At most
2000 messages are pending and at most 10^4 calls are made.
Design a Delayed Priority Queuemedium