@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 <[email protected]>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 <[email protected]> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
