7

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.

Charles
  • 50,943
  • 13
  • 104
  • 142
Raj
  • 241
  • 4
  • 12
  • 2
    Here's a hint: draw the real number line, and mark above it the "life lines" of the elephants. Notice that you only care which points open an inteval, which close an interval, and their order. – StoryTeller - Unslander Monica Sep 18 '12 at 18:59

5 Answers5

8

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.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
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?

Coding Mash
  • 3,338
  • 5
  • 24
  • 45
CyberGuy
  • 2,783
  • 1
  • 21
  • 31
  • Thanks. Its a neat trick to handle the issue of overlapping. The array in turn represents a real number line form where we are marking the time periods (by increment of elements). I am trying to come up with other solutions but so far this seems to be the best idea to work on. – Raj Sep 18 '12 at 19:58
0

This is similar to a program that checks to see if parenthesis are missing. It is also related to date range overlap. This subject is beaten to death on StackOverflow and elsewhere. Here it is:

Determine Whether Two Date Ranges Overlap

I have implemented this by placing all of the start/end ranged in one vector of structs (or classes) and then sorting them. Then you can run through the vector and detect transitions of the level of elephants. (Number of elephants -- funny way of stating the problem!)

Community
  • 1
  • 1
bspikol
  • 96
  • 6
0

From your Input I find that all the time period are overlapping then in that case the solution is simple

we have been given range as [start end]

so the answer will be maximum of all start and minimum of all end.

Just traverse over each time period and find the maximum of all start and mimumum of all end

Note : this solution is applicable when all the time periods over lap

In Your example Maximum of all input = 6 Minimum of all output= 7

selftaught91
  • 7,013
  • 3
  • 20
  • 26
0

I will just make two arrays , one for the time elephants are born and one for the time elephants die . Sort both of the arrays.

Now keep a counter (initially at zero ) . Start traversing both the arrays and keep getting the smallest element from both of the arrays. If we get an element from start array then increment the counter , else decrement the counter. We can find the max value and the time easily by this method.

Knightbarron
  • 35
  • 2
  • 10