Reserve Stock Under Expiring Holds
During a sale, an online store must never sell a unit it does not have. When a shopper starts checking out, the store puts a hold on the units in their cart for holdMinutes minutes. If they pay in time, the held units are sold. If they abandon the checkout, the hold expires and the units go back on sale.
You are given one product's starting stock and a log of events in time order. Event i happens at minute times[i], has the action actions[i], and refers to the hold holdIds[i]:
"hold": a new hold asks forquantities[i]units. It is granted when at least that many units are available, and then those units are no longer available. Otherwise it is rejected and nothing changes. A granted hold placed at minutetexpires at minutet + holdMinutes."checkout": the shopper pays. It succeeds when the hold is still active; its units are then sold for good."release": the shopper empties the cart. It succeeds when the hold is still active; its units become available again immediately.
A hold stops being active when it expires, is checked out or is released. A hold that expires at minute m is already expired for every event at minute m or later, and its units are available again for those events.
Return an array with one boolean per event: whether a hold was granted, or whether a checkout or release succeeded.
Example
stock = 5, holdMinutes = 10, and the events:
| minute | action | hold | quantity | |---|---|---|---| | 0 | hold | 1 | 3 | | 2 | hold | 2 | 3 | | 5 | checkout | 1 | 0 | | 6 | hold | 3 | 2 | | 16 | hold | 4 | 1 | | 17 | checkout | 3 | 0 | | 18 | release | 4 | 0 |
Hold 1 takes 3 of the 5 units, so hold 2 cannot have 3 and is rejected. Hold 1 checks out: 3 units are sold. Hold 3 takes the last 2. At minute 16 hold 3 has expired (it was placed at 6), so its 2 units are back and hold 4 is granted. Checking out hold 3 at minute 17 fails, and releasing hold 4 succeeds. The answer is [true, false, true, true, true, false, true].
[ "5", "10", "[0,2,5,6,16,17,18]", "[\"hold\",\"hold\",\"checkout\",\"hold\",\"hold\",\"checkout\",\"release\"]", "[1,2,1,3,4,3,4]", "[3,3,0,2,1,0,0]" ]
Explanation. The example.
[ "1", "5", "[0,5,5,9]", "[\"hold\",\"hold\",\"checkout\",\"checkout\"]", "[1,2,1,2]", "[1,1,0,0]" ]
Explanation. A hold placed at 0 has expired at minute 5.
[ "3", "100", "[1,2,3]", "[\"hold\",\"checkout\",\"hold\"]", "[1,1,2]", "[4,0,3]" ]
Explanation. A rejected hold cannot be checked out.
[ "2", "60", "[0,1,2,2,3,4]", "[\"hold\",\"hold\",\"release\",\"hold\",\"release\",\"checkout\"]", "[1,2,1,3,1,3]", "[2,1,0,2,0,0]" ]
Explanation. Releasing frees the units at once; a hold cannot be released twice.
[ "1", "1", "[0,0,0]", "[\"checkout\",\"release\",\"hold\"]", "[99,99,7]", "[0,0,1]" ]
Explanation. An id that was never held fails.
[ "4", "3", "[0,0,1,1,2,3,4,4,7]", "[\"hold\",\"hold\",\"hold\",\"hold\",\"hold\",\"hold\",\"hold\",\"checkout\",\"hold\"]", "[1,2,3,4,5,6,7,6,8]", "[1,1,1,1,1,2,2,0,1]" ]
Explanation. Several holds expire at once, and units that were checked out never come back.
[ "5", "10", "[0,1,2,3,20,20]", "[\"hold\",\"checkout\",\"release\",\"hold\",\"checkout\",\"hold\"]", "[1,1,1,2,2,3]", "[2,0,0,3,0,3]" ]
Explanation. A sold hold cannot be released; a late checkout fails and its units are on sale again.
[ "1", "1", "[5]", "[\"hold\"]", "[1]", "[1]" ]
Explanation. A single event.
Follow-up: Holds now have different lengths: a Prime member's cart is held for 30 minutes and everyone else's for 10. Which part of your solution stops working, and what do you replace it with?
- `1 <= stock <= 10^9` - `1 <= holdMinutes <= 10^4` - `1 <= times.length <= 10^5`, and all four arrays have the same length. - `0 <= times[i] <= 10^9`, and `times` is non-decreasing. Events at the same minute happen in array order. - `actions[i]` is `"hold"`, `"checkout"` or `"release"`. - Every `hold` event has an id no other `hold` event uses. A `checkout` or `release` may name an id that was never granted, and then it fails. - `1 <= quantities[i] <= 10^4` for a `hold`, and `quantities[i] = 0` otherwise.
- Views
- 2