algorithm - 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

Following must work:

1. Sort all your time values 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