@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 year seperately
2. increment the birth year till we get a value of year which is
equal to first death year, keep count of current elephant alive in a value
MAX_ELE.
3. Now as one element died decrement one count and increment till
we get a year value in birth list which is greater or equal to second death
date, keep track of elephents alive and if it is greater than
previous,update MAX_ELE with current elephant count
4. continue till birth list empty
sorting will require O(nlogn) and finding year in which max elephents were
alive will take O(n).Total complexity O(nlogn)
Correct me anything wrong
--
Regards
Jitendra Kushwaha
Undergradute Student
Computer Science & Eng.
MNNIT, Allahabad
--
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.
