Colleagues, how about the following?
At each start point, the total number of leaving elephants increases by
one; at each end point, it decreases by one. We:
1. form a vector of pairs: {5, +1}, {10, -1}, {6, +1}, {15, -1}, {2, +1},
{7, -1} ... -- this takes O(N) time and O(N) additional space
2. Sort this vector by a) ascending .first; b) descending .second (so that
if at the same time there are both newborn and just dead elephants, we
count the overall number properly) -- O(N* logN)
3. Scan the sorted vector keeping maximal value of the counter -- O(N)
int maxcount = 0, count = 0, index = 0;
for (i = 0; i < v.size(); ++i) {
count += v[i].second;
if (count > maxcount) {
maxcount = count; index = i;
}
}
4. print 'maxcount' between v[index] and v[index+1]
On Thursday, February 21, 2013 4:40:17 AM UTC-5, NITHIN HOTKER wrote:
>
> Given life time of different elephants find *period when maximum number
> of elephants lived.*
> Eg [5, 10], [6, 15], [2, 7] etc. year in which max no elephants exists.
>
> When this is put on paper the answer is [6,7] .
>
> Is it* [Max(start interval),Min(end interval)] * such that start < end
> interval ?? I've checked this for 2-3 cases and it works .
>
> Given another interval , find set of intervals in which given point lies .
> This could be done using augumented data-structure using Tree .
>
> Let's create a balanced BST using the asc order {2,5,6,7,10,15}
>
> What after this ???
>
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
