Painting the Walls
Hard · Dynamic Programming · about 30 minutes
Asked at Google, Amazon, Snowflake, Microsoft, CrowdStrike.
n walls: a paid painter paints wall i in time[i] units for cost[i]. A free painter paints any wall in 1 unit for free, but only while the paid painter is busy. Return the minimum cost to paint all walls.