liyupku2000
BAN USERGreat! I believe this is the optimal solution.
- liyupku2000 February 04, 2013@Biru: After sorting, we only need to go through both the birth times and the death times once, so it is O(N lgN). When you check a year, the number of lives = the number of births b4 - the number of deaths b4.
- liyupku2000 February 02, 2013to Kevin: I have read it carefully, maybe you misunderstood my question. Of course the death times should be considered, but we can only check birth times because
" at least 1 birth time will be present when the maximum number of dinosaurs were alive ". Am I right?
Sort birth times and death times independently. Check each birth time from left side, as well as you can easily count how many death times there have been.
- liyupku2000 February 02, 2013Why not just check birth times?
- liyupku2000 February 02, 2013Comment:
The problem is same as: count the number of (a, k) that a | k where 1<= k <= N.
The complexity is O(sqrt(N)).
It's O(n^2) no matter the numbers are pos or neg. By tracking the largest value (say it's 'x') among the first items of n arrays, go ahead (just check the items one by one in the other n-1 arrays, binary search can be used for speeding up, but need careful design -- "parallelly" run with simple go-through) to find the items that >= x in all arrays. If all item == x, then we find a common value; otherwise, start a new iteration. It's O(n^2) because each item was checked only by once.
- liyupku2000 February 04, 2013