Orders by deadline

heap hash table scheduling interviews

A delivery service receives orders, each with a deadline by which it has to be fulfilled (an integer, for example a minute number). Different orders can have the same deadline. The dispatcher needs four operations:

+ d, an order with deadline d has arrived;
- d, one order with deadline d has been cancelled; if there are no such orders, nothing happens;
? d, is there currently at least one order with deadline d;
min, the earliest deadline among the orders now waiting.

Process a log of operations.

Input

The first line holds q (1 ≤ q ≤ 2·10⁵). Then q lines with operations; 0 ≤ d ≤ 10⁹.

Output

For each ? operation, a line yes or no; for each min, the earliest deadline, or - if there are no orders.

Examples

Example 1

Input

13
+ 20
+ 5
+ 5
min
- 5
? 5
min
- 5
? 5
min
- 7
- 20
min

Output

5
yes
5
no
20
-

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Each operation needs its own structure. Which one answers “is there such a deadline” in O(1), and which “the earliest” in O(log n)? Can you keep both at once?

2The idea

A dictionary “deadline → how many orders have it” answers ? and handles a cancellation in O(1). A binary heap of deadlines answers min, but deleting from the middle of a heap is expensive. So a cancellation leaves the heap alone: stale entries stay in it. When the minimum is asked for, deadlines that the dictionary no longer has are thrown off the top of the heap: this is lazy deletion.

3Walkthrough

Why this is fast: each deadline added gets into the heap once and is thrown out of it at most once, so all the throwing out together costs O(q log q), however it is spread over the queries. The dictionary is always accurate, and the heap is needed only for order. Equal deadlines take care of themselves: the heap has several entries with one deadline, the dictionary their number, and an entry is thrown out only when the number has become zero.

A solution on a single list is correct, but in, remove and min go through the whole list. In the fifth test tens of thousands of orders are waiting at once, and each of 150 thousand operations costs tens of thousands of steps. Which structure for which operation, and what each costs in a measurement, is in the article “Choosing a data structure”.

3+Solution

4Complexity

O(q log q) time and O(q) memory: the heap may also hold cancelled deadlines, but no more than were added.

5Common mistakes

A single list. Correct, but O(q) per operation.
A set instead of a counter. Two orders with deadline 5, one cancelled: deadline 5 must remain. The sample checks this.
Cancelling what does not exist. The counter must not go negative: otherwise the next order with that deadline becomes “invisible”.

Algorithms behind it

TEC Technique Choosing a data structure First the list of operations, then the structure: the cost of each operation in Python and Go on one map. depends on the choice 1 problem DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems DS Data structure Hash table Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell. O(1) on average 2 problems