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

Question

I came across an interview question:

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

I wonder if this problem could be related to the longest substring problem for the "n" number of rows, so that each row represents a continuous range of time period.

For example, for example: [5,10] <=> 5 6 7 8 9 10

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

Any help would be appreciated.

Answer 1

For each elephant, create two events: the elephant was born, the elephant died. Sort events by date. Now go through the events and just keep counting how many elephants are alive; every time you reach a new maximum, write down the start date and every time you drop from the maximum record to the end date.

This decision is independent of whether the dates are integers.

Answer 2

If I were in an interview, I would create a std::array with the maximum age elephant, and then increase the number of elements for each elephant, for example:

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

Then I would sort and find where the largest number is.

It is possible to use std::map as map<int,int> (1st, 2nd - the number of elephants). It will be sorted by default.

I am wondering if you know any better solution?

Answer 3

This is similar to a program that checks for parentheses. This is also due to overlapping date ranges. This item has been beaten to death in StackOverflow and elsewhere. Here he is:

Determine if two date ranges overlap

I implemented this by putting the entire start / end into one vector of structures (or classes), and then sorting them. Then you can run through the vector and detect elephant level transitions. (The number of elephants is a fun way to report a problem!)

Answer 4

From your input, I found that the entire time period overlaps, then in this case the solution is simple

we are given a range as [start end]

therefore, the answer will be maximum for all initial and minimum values ​​of the end.

Just go through each period of time and find the maximum of all starts and the maximum of all ends

Note: this solution is applicable if all laps

In your example, Maximum input = 6 Minimum output = 7