On Feb 23, 2:05 am, Ridvan <[EMAIL PROTECTED]> wrote:
> > I see no reason to use a sorted heap, a plain list
> > of ranges would do as well.
>
> This will lead to O(N) algo, i prefer O(lgN).
I'm not sure why you think a plain list would be O(N). It seems to me
that it would be O(1).
> > Once again, why? Even if you a heap sorted by range size,
> > just take the smallest one, and pick the min value. After
> > reducing the range by one, if it's zero - get rid of it,
> > otherwise, the heap will still be sorted by size since
> > the smallest range will still be the smallest.
>
> I like this solution it will be faster, but I see a small error
> instead of decreasing the min you should increase it, or decrease the
> max.
Note that he did not say to decrease the min. He said to decrease the
range. You would do that by increasing the min, since range = max -
min or max - min + 1 depending on exactly what you store.
Dave
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
