Find the time period with the maximum number of overlapping intervals

Question

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

I tried hard to solve this, but I am unable to do so.

How can I solve this problem?

I got approach for when a user asks to find the number of elephants in any year. I solved that by using segment tree, whenever any elephants time span given, increase every year of that time span by 1. We can solve that in this way. Can this be used to solve the above problem?

For above question, I only need the high-level approach, I will code it myself.

Answer 1

• 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