## Wednesday, January 22, 2014

### Problem

There is one very famous problem. I am asking the same here. There is number of elephants time span given, here time span means, year of birth to year of death. You have to calculate the period where maximum number of elephants are alive.

Example :
1990 - 2013
1995 - 2000
2010 - 2020
1992 - 1999

### Solution

Pseudocode
• Split each date range into start date and end date.
• Sort the dates. If a start date and an end date are the same, put the end date first (otherwise you could get an empty date range as the best).
• Iterate through the dates using a sweep-line algorithm:
• If you get a start date:
• Increment the count.
• If the current count is higher than the last best count, set the count, store this start date and set a flag.
• If you get an end date:
• If the flag is set, store the stored start date and this end date with the count as the best interval so far.
• Reset the flag.
• Decrement the count.
Example:
For input:
1990 - 2013
1995 - 2000
2010 - 2020
1992 - 1999
Split and sorted: (S = start, E = end)
1990 S, 1992 S, 1995 S, 1999 E, 2000 E, 2010 S, 2013 E, 2020 E

Iterating through them:
count = 0
lastStart = N/A
1990: count = 1
count = 1 > 0, so set flag
and lastStart = 1990

1992: count = 2
count = 2 > 0, so set flag
and lastStart = 1992

1995: count = 3
count = 3 > 0, so set flag
and lastStart = 1995

1999: flag is set, so
record [lastStart (= 1995), 1999] with a count of 3
reset flag
count = 2

2000: flag is not set
reset flag
count = 1

2010: count = 2
since count = 2 < 3, don't set flag

2013: flag is not set
reset flag
count = 1

2020: flag is not set
reset flag
count = 0

What if the number of elephants are very large?
For a (very) large number of elephants, it might be worth skipping the sort. You could create an array indexed by year with +1 for birth, -1 for death. O(e) to fill, and O(n) to sweep, where e is number of elephants and n is date range.

Reference