Promotion Price Calendar
MediumIntervals · Walmart
A store has a base price for each item and a calendar of promotions. You are given:
base_prices: a dict mapping SKU to its regular integer price.promotions: a list of[sku, start, end, promo_price]. The promotion is active at every timetwithstart <= t <= end(inclusive). Promotions for the same SKU may overlap.queries: a list of[sku, ts].
For each query, the price of sku at time ts is the lowest of its base price and the prices of all its promotions active at ts. A promotion priced above the base price therefore never raises the price. If sku is not in base_prices, the answer is the string "NONE" (promotions for such SKUs are ignored).
Return a list with one answer per query, in query order. Queries are not sorted, and checking every promotion for every query is too slow at the given limits.
Example 1
- Input:
- base_prices = {"tv": 500, "radio": 40}, promotions = [["tv", 1, 10, 450], ["tv", 5, 7, 420], ["radio", 3, 3, 45]], queries = [["tv", 6], ["tv", 8], ["radio", 3], ["tv", 11], ["phone", 1]]
- Output:
- [420, 450, 40, 500, "NONE"]
- Explanation
- At time 6 both TV promotions are active and 420 is lowest. At 8 only the 450 promotion is left. The radio promotion is above base, so 40 stands. At 11 no TV promotion is active.
phonehas no base price.
Example 2
- Input:
- base_prices = {"a": 10}, promotions = [["a", 2, 4, 8]], queries = [["a", 1], ["a", 2], ["a", 4], ["a", 5]]
- Output:
- [10, 8, 8, 10]
- Explanation
- The promotion covers times 2 through 4 including both ends, so only the queries at 2 and 4 get the price 8.
Example 3
- Input:
- base_prices = {}, promotions = [["x", 0, 9, 1]], queries = [["x", 5]]
- Output:
- ["NONE"]
- Explanation
xhas a promotion but no base price, so it is not a sellable item and the answer is"NONE".
Constraints
0 <= promotions.length, queries.length <= 10^50 <= start <= end <= 10^9and0 <= ts <= 10^91 <= base price, promo_price <= 10^6- SKUs are non-empty strings