@chinna: the question asks for first fit, not best fit
On Sun, May 22, 2011 at 1:03 AM, pacific :-) <pacific4...@gmail.com> wrote:
> @ankit: I didn't undertand ur explanation for why a sort wont work.
>
> 1. Sort the bins by the left over space.
> 2. For a new value to be inserted , do a binary search and locate the best
> fit.
> 3. For the bucket we are adding this new element , its left over space
> reduces ...so now do a binary search to find its new location and move it to
> the new location.
>
> O(nlogn) {for initial sort} + n * { logn (for search ) + logn (for moving
> the box to which we are adding ) }
> Total complexity = O(nlogn)
>
> Correct me if i'm wrong.
>
> On Tue, May 17, 2011 at 7:05 PM, ankit sambyal <ankitsamb...@gmail.com>wrote:
>
>> @monsieur: we can't solve the problem by the way u suggest because we
>> have to sort it by bin number but we have to find the first fit according to
>> the left over space in the bin. So, in the worst case it will take more than
>> O(n*log(n))time.... If u need any clarifications feel free to comment
>>
>>
>> regards,
>> Ankit
>>
>>
>>
>>
>>
>>
>> On Tue, May 17, 2011 at 5:52 AM, MONSIEUR <monsieur....@gmail.com> wrote:
>>
>>> guys why cant we simply sort bins using merge sort or any comparison
>>> sort and then use binary search to find out the first available
>>> bin.t(n)=O(nlgn)+n*(lgn)=O(nlgn).
>>>
>>> --
>>> 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.
>>>
>>>
>> --
>> 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.
>
--
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.
