Find the time period with the maximum number of overlapping intervals

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

Answer is   1995 - 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).
• Start with a count of 0.
• 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

• http://stackoverflow.com/questions/19155454/find-the-time-period-with-the-maximum-number-of-overlapping-intervals