Finding (number of) overlaps in a list of time ranges

Question

Given a list of time ranges, I need to find the maximum number of overlaps.

Following is a dataset showing a 10 minute interval of calls, from which I am trying to find the maximum number of active lines in that interval. ie. from the example below, what is the maximum number of calls that were active at the same time:

CallStart   CallEnd
2:22:22 PM  2:22:33 PM
2:22:35 PM  2:22:42 PM
2:22:36 PM  2:22:43 PM
2:22:46 PM  2:22:54 PM
2:22:49 PM  2:27:21 PM
2:22:57 PM  2:23:03 PM
2:23:29 PM  2:23:40 PM
2:24:08 PM  2:24:14 PM
2:27:37 PM  2:39:14 PM
2:27:47 PM  2:27:55 PM
2:29:04 PM  2:29:26 PM
2:29:31 PM  2:29:43 PM
2:29:45 PM  2:30:10 PM

If anyone knows an alogrithm or can point me in the right direction, I would be grateful.

TIA,

Steve F

Answer 1

How about a naive approach:

• Take the least of the start times and the greatest of the end times (this is your range R)
• Take the shortest call duration -- d (sorting, O(nlog n))
• Create an array C, of ceil(R/d) integers, zero initialize
• Now, for each call, add 1 to the cells that define the call's duration O(n * ceil(R/d))
• Loop over the array C and save the max (O(n))

I guess you could model this as a graph too and fiddle around, but beats me at the moment.

Answer 2

Following must work:

1. Sort all your time valuess and save Start or End state for each time value.
2. Set numberOfCalls to 0 (count variable)

3. Run through your time values and:

   • increment numberOfCalls if time value marked as Start
   • decrement numberOfCalls if time value marked as End
   • keep track of maximum value of numberOfCalls during the process (and time values when it occurs)

Complexity: O(n log(n)) for sorting, O(n) to run through all records

Answer 3

You short the list on CallStart. Then for each element (i) you see for all j < i if

CallEnd[j] > CallStart[i] // put it in a map with CallStart[i]  as the key and some count

Rest should be easy enough.

Answer 4

In my opinion greedy algorithm will do the needful. The problem is similar to find out the number of platforms required for given trains timetable. So the number of overlaps will be the number of platforms required.
callStart times are sorted. Start putting each call in an array(a platform). So for call i and (i + 1), if callEnd[i] > callStart[i+1] then they can not go in the same array (or platform) put as many calls in the first array as possible. Then repeat the process with rest ones till all calls are exhausted. In the end, number of arrays are maximum number of overlaps. And the complexity will be O(n).

Answer 5

It's amazing how for some problems solutions sometimes just pop out of one mind... and I think I probably the simplest solution ;)

You can represent the times in seconds, from the beginning of your range (0) to its end (600). A call is a pair of times.

Python algorithm:

def maxSimultaneousCalls(calls):
  """Returns the maximum number of simultaneous calls
  calls   : list of calls
    (represented as pairs [begin,end] with begin and end in seconds)
  """
  # Shift the calls so that 0 correspond to the beginning of the first call
  min = min([call[0] for call in calls])

  tmpCalls = [(call[0] - min, call[1] - min) for call in calls]
  max = max([call[1] for call in tmpCalls])

  # Find how many calls were active at each second during the interval [0,max]
  seconds = [0 for i in range(0,max+1)]
  for call in tmpCalls:
    for i in range(call[0],call[1]):
      seconds[i] += 1

  return max(seconds)

Note that I don't know which calls were active at this time ;)

But in term of complexity it's extremely trivial to evaluate: it's linear in term of the total duration of the calls.

Answer 6

The following page has examples of solving this problem in many languages: http://rosettacode.org/wiki/Max_Licenses_In_Use