Promo code cart discount
A checkout engine applies promo codes to one cart. prices_cents[i] is what item i costs. Promo j arrives in two parallel lists: min_cents[j] is the lowest price an item may carry for that promo to apply to it, and off_cents[j] is what the promo takes off. A promo attaches to at most one item, an item accepts at most one promo, and off_cents[j] never exceeds min_cents[j]. Return the largest total number of cents the engine can take off this cart. The two promo lists have the same length as each other, prices are positive, and any list may be empty. Handing the biggest promo to the most expensive item it fits is not always the best move.
max_promo_savings(prices_cents: list[int], min_cents: list[int], off_cents: list[int]) → int[[10000,50000],[50000,10000],[5000,6000]]out11000[[500],[1000],[100]]out0State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[10000,50000],[50000,10000],[5000,6000]]11000not run yetsample[[500],[1000],[100]]0not run yetsample