Shopping Cart Minimum Billing

Problem Compute the minimum bill for a cart. Each product is [price, tag1, tag2, …] (tags may be "EMPTY"). Each discount is [tag, type, amount]: type 0 → the price becomes amount; type 1 → amount% off retail; type 2 → amount subtracted from retail. For each product apply the single best (cheapest) discount among those matching its tags; truncate each discounted price to an integer; sum them.

Input / Output

• Input: products[][], discounts[][].
• Output: integer total minimum cost.

Constraints

• Products and discounts up to 10^3–10^5 scale — index discounts by tag in a hash map rather than scanning per product.

Example

• Product [100, "sale"], discounts [["sale",1,10],["sale",2,5]] → min(90, 95) = 90.

Expected approach

• Build tag → list of discounts map. Per product, start at retail; for each tag, evaluate each candidate discount (type 0: amount; type 1: price*(100−amount)/100; type 2: price−amount), keep the minimum, truncate, accumulate. Watch: products with EMPTY tags pay retail, floors not rounding, discounts never taken below 0 (clarify). O(total tags + discounts).