I think you can do this in O(n) time. Feel free to correct me where
I'm wrong.
Create a 2D array with years on one side and elephant's time alive on
the other. example:
2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012
E1 1 1 1 1 1 1 1 1 1
E2 1 1 1 1
1 1 1 1 1
E3 1 1
1 1
Now for every years add vertical indices example 2006 = 3, 2007 = 3,
2008 = 3 and so on. This will give you the
year with max elephant population. The array can be init with 0 or a
static array can be used.
@Anurag: How will you approach this problem by using LCA algorithm
that your link leads to?
On Jun 5, 6:16 am, amit <[email protected]> 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 [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.
