Menu
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
216
Overlap = min(A2, B2) - max(A1, B1) + 1. In other words, the overlap of two integer intervals is a difference between the minimum value of the two upper boundaries and the maximum value of the two lower boundaries, plus 1.
You can do this by swapping the ranges if necessary up front. Then, you can detect overlap if the second range start is: less than or equal to the first range end (if ranges are inclusive, containing both the start and end times); or. less than (if ranges are inclusive of start and exclusive of end).
Following must work:
numberOfCalls to 0 (count variable)Run through your time values and:
Complexity: O(n log(n)) for sorting, O(n) to run through all records
147
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
