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
use interval trees.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Sat, Jun 5, 2010 at 6:16 PM, 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..
@Amit :
Query 1 : It can be solved in O(n) by checking which elephants life span
contain the given year
Query 2 : Picking up the fact that a elephant die only after its birth we
can find the second query in O(nlogn)
ALGO:
1. sort in increasing order birth year and death