i think this can be done in O(nlogn)
create an array of the years that elephants are born and the years that they die
in this case it would be {2000,2008,2004,2012,2006,2009}
each object in your array should contain both the year and a flag to
know we should increment the number of elephants at this year or
decrement it
sort them by year in O(nlogn)
you can handle the number of elephantst in O(n)
so the overall would be O(nlogn)On 6/5/10, amit <amitjaspal...@gmail.com> wrote: > Maximum number of elephants alive > Hello guyz, > > Every elephant has a birth_time and a death_time. Given N Elephants > with birth times and death times.. How can we find > 1) the maximum number of elephants that can be alive at any given > point of time. > 2) what is the year in which you can have maximum number of elephants > alive. > ex: E1 - 2000-2008 E2-2004-2012 E3-2006-2009 > So in 2006 you have 3 elephants alive (maximum) > PS: ignore months and all stuff .. if a elephants live in a year > consider it lives that complete year > > I have O(year_max-year_min) solution and O(n^2) solution , where > n=number of elephants . > Can we do better ?? > > thanks > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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.
