Parcel Lockers
Medium · heap
A building has n parcel lockers, numbered 1 to n, and all of them start empty. Events happen in the order given. For event k, actions[k] is either "deliver" or "collect", and ids[k] is the number of the parcel involved.
"deliver": the parcel is put into the lowest-numbered empty locker. If every locker is full, the parcel is turned away and is not stored anywhere."collect": the owner takes the parcel, and its locker becomes empty. If the parcel is not in a locker (it was turned away, or already collected), nothing happens.
Return a list with one number for every "deliver" event, in order: the number of the locker the parcel was put in, or -1 if it was turned away. A parcel number can be delivered again after it has been collected or turned away.
Examples
Example 1
Input: n = 2, actions = ["deliver", "deliver", "deliver", "collect", "deliver"], ids = [10, 11, 12, 10, 13]
Output: [1, 2, -1, 1]
Parcels 10 and 11 fill lockers 1 and 2. Parcel 12 is turned away. Collecting parcel 10 frees locker 1, which parcel 13 then takes.
Example 2
Input: n = 3, actions = ["deliver", "deliver", "collect", "deliver", "collect", "deliver"], ids = [5, 6, 5, 7, 6, 8]
Output: [1, 2, 1, 2]
Locker 1 is freed and reused by parcel 7. When parcel 6 leaves locker 2, parcel 8 takes it.
Example 3
Input: n = 1, actions = ["collect", "deliver", "deliver"], ids = [4, 4, 9]
Output: [1, -1]
Collecting a parcel that was never stored does nothing. Parcel 4 takes the only locker, so parcel 9 is turned away.
Constraints
- 1 <= n <= 2000
- 1 <= len(actions) <= 10^4
- len(ids) == len(actions)
- actions[k] is "deliver" or "collect"
- 1 <= ids[k] <= 10^9
- A deliver never uses the number of a parcel that is currently in a locker