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.
