Given the life time of different elephants, find the period when maximum number of elephants lived

Question

I came across an interview question:

"Given life times of different elephants. Find the period when maximum number of elephants were alive." For example:
Input: [5, 10], [6, 15], [2, 7]
Output: [6,7] (3 elephants)

I wonder if this problem can be related to the Longest substring problem for 'n' number of strings, such that each string represents the continuous range of a time period.

For e.g: [5,10] <=> 5 6 7 8 9 10

If not, what can be a good solution to this problem ? I want to code it in C++.

Any help will be appreciated.

Answer 1

For each elephant, create two events: elephant born, elephant died. Sort the events by date. Now walk through the events and just keep a running count of how many elephants are alive; each time you reach a new maximum, record the starting date, and each time you go down from the maximum record the ending date.

This solution doesn't depend on the dates being integers.

Answer 2

If i were you at the interview i would create a std::array with maximum age of the elephant and then increment elements number for each elephant like:

[5,10] << increment all elements from index 5 to 10 in array.

Then i would sort and find where is the biggest number.

There is possibility to use std::map like map<int,int> ( 1st - period, 2nd - number of elephants). It will be sorted by default.

Im wondering if you know any better solution?