$$ Details

Given a set of $n$ objects of sizes $s_0,s_1,$dots,$s_{n-1},$ each satisfying $n0,1,$dots,$k-1k0,$ and $an$ unlimited supply $of$ bins $of$ capacity $1,$ pack all $n$ objects into bins such that the total size $of$ the objects $in$ each bin does not exceed $1$ and the number $of$ bins $is$ minimized.

Consider the following greedy algorithm: Assume you have already placed objects $0,1,$dots,$k-1.$ Place object $kin$ a bin that has the maximum amount $of$ available space. $Ifno$ such bin exists, place the object $in$ a new bin.

Describe how $to$ efficiently implement this algorithm using a binary heap.

Analyze the runtime $of$ this algorithm.

Show that this greedy algorithm does not always return the optimal solution.