Merge bars to fit
A dashboard draws one bar per hour of a build log, but the widget can only show max_bars bars. While there are too many bars it repeatedly merges the adjacent pair whose combined height is smallest into a single bar of that combined height, and a tie goes to the leftmost such pair. Merging shortens the row by one, and a merged bar can then be merged again with a neighbour. Return the bar heights that remain, left to right. When max_bars is at least the number of bars, return the heights unchanged, and when max_bars is below 1 treat it as 1.
collapsed_bar_heights(heights: list[int], max_bars: int) → list[int][[4,1,1,4,3],3]out[6,4,3][[5,2],5]out[5,2][[3,3,3,3],1]out[12]State 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.
[[4,1,1,4,3],3][6,4,3]not run yetsample[[5,2],5][5,2]not run yetsample[[3,3,3,3],1][12]not run yetsample