i think we can use heaps for this problem..bring to the root which has capacity to hold and pick the root each time. If the root cannot accomodate then no other node will be able to accomodate.
On Sat, May 14, 2011 at 1:26 AM, MK <stardust...@gmail.com> wrote: > Consider the first fit strategy for online bin packing. > > So if you have N bins numbered 1, 2, 3..N and you are given value V, > you scan them from left to right and insert V into the first bin that > currently has enough capacity. > > In the naieve case, N insertions will take O(N^2) time. > > How can this be done in NlogN time? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- regards, chinna. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
