Cheapest render hour booking
A game studio books cloud render hours a month at a time. Booking one hour during month m costs price_cents[m], and the vendor will sell at most cap_hours[m] hours in that month. The studio burns need_hours[m] hours during month m. Hours booked before the month they are burned sit in the account and cost carry_cents each for every month they are held, so an hour booked in month s and burned in month t costs price_cents[s] plus carry_cents times (t - s). An hour can never be booked after it is burned. The three lists have the same length, and the caps always allow every month's burn to be covered. Return the smallest total spend in cents.
min_render_spend(price_cents: list[int], cap_hours: list[int], need_hours: list[int], carry_cents: int) → int[[500,200,900],[4,4,4],[2,2,2],30]out1860[[100,300],[2,9],[0,5],10]out1120State 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.
[[500,200,900],[4,4,4],[2,2,2],30]1860not run yetsample[[100,300],[2,9],[0,5],10]1120not run yetsample