All problems

Day-Old Bakery

Medium · design

A bakery counter holds loaves of bread. Each loaf has an id, a price, and a sell_by time: it can be sold only at times strictly before sell_by. The counter starts empty, and you are given a list of operations to perform in order. operations[i] is a word and args[i] is the list of numbers that go with it:

• "add" with [id, price, sell_by] puts a loaf on the counter. If a loaf with the same id is already on the counter, it is replaced by this one.
• "remove" with [id] takes the loaf with that id off the counter. If there is none, nothing happens.
• "sell" with [now] sells one loaf at time now: the most expensive loaf on the counter whose sell_by is greater than now. If several loaves share the highest price, the one with the smallest id is sold. A sold loaf leaves the counter. Loaves that are too old to sell stay out of the way and are never sold.

The times in "sell" operations never go down from one "sell" to the next.

Return a list with one number for each "sell" operation, in order: the id of the loaf that was sold, or -1 if no loaf could be sold.

Examples

Example 1

Input: operations = ["add", "add", "sell", "sell", "sell"], args = [[1, 50, 10], [2, 70, 10], [3], [4], [5]]

Output: [2, 1, -1]

The loaf with id 2 is the most expensive, so it is sold first. Then loaf 1 is sold. The counter is empty for the last sale.

Example 2

Input: operations = ["add", "add", "sell", "sell"], args = [[1, 90, 5], [2, 40, 20], [6], [7]]

Output: [2, -1]

At time 6 the 90-coin loaf is too old, so the 40-coin loaf is sold. Nothing is left at time 7.

Example 3

Input: operations = ["add", "add", "add", "remove", "add", "sell", "sell"], args = [[4, 30, 9], [7, 30, 9], [4, 10, 9], [7], [7, 25, 9], [1], [1]]

Output: [7, 4]

Adding id 4 a second time replaces the 30-coin loaf by a 10-coin one, and loaf 7 is removed and then added again at 25 coins. Loaf 7 is the most expensive, then loaf 4.

Constraints

• 1 <= len(operations) <= 20000
• len(args) == len(operations)
• operations[i] is one of add, remove, sell
• 0 <= id <= 10^9
• 1 <= price <= 10^9
• 0 <= sell_by <= 10^9
• 0 <= now <= 10^9, and the values of now never decrease between sell operations.