Assign Pins to Shortest Columns
Pinterest's home feed lays pins out in k vertical columns. Pins arrive one at a time in feed order; each pin i has height heights[i]. Each arriving pin is placed at the bottom of the column whose current total height is smallest; ties go to the leftmost such column.
Return the column index assigned to each pin.
Example:
heights = [5, 3, 4, 2], k = 2 pin0 -> col0 (both 0, leftmost) cols: [5, 0] pin1 -> col1 (0 < 5) cols: [5, 3] pin2 -> col1 (3 < 5) cols: [5, 7] pin3 -> col0 (5 < 7) cols: [7, 7] answer: [0, 1, 1, 0]
Hints
Hint 1
Track each column's running height; every pin goes to the current minimum. A scan per pin is O(n·k); a min-heap of (height, columnIndex) makes it O(n log k).
Hint 2
Ordering pairs by height first and column index second makes the leftmost-on-tie rule fall out of the comparison for free.