1. have an array of N years. starting with first year and ending at last year.
O(N) space here. initialise all elements to zero.
2. Take array of E and birthyear first. Whenever you encounter new
birthyear, do array[year]++.
3. Take array of E and deathyear now. Whenever you encounter new
deathyear, do array[year]--.
4. Parse this array of year. sum_for_given_year += array[year]
To me, it looks like O(N).
Correct me if I am wrong.
On Sun, Jun 6, 2010 at 7:56 PM, Anurag Sharma anuragvic...@gmail.com wrote:
I am sorry for the link if it caused any confusion. It was just a part of
the signature. Kindly disregard the link in this context.
Anurag Sharma
On Sun, Jun 6, 2010 at 7:55 AM, Minotauraus anike...@gmail.com wrote:
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 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.
--
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.
