Calculating the maximum number of busy channels in a phone system

Question

I am trying to come up with an algorithm for calculating the maximum number of busy channels in the telephone system. There is a Call Data Registration (CDR) file, which specifies the begin (TB) and end (TE) time of each call. From it one can build an array T: ( (T1B, T1E), (T2B, T2E), (T3B, T3E), (T4B, T4E), (T5B, T5E), (T6B, T6E), (T7B, T7E), (T8B, T8E), (T9B, T9E) ) Multiple calls can occur simultaneously. Each call occupies one channel. Example is in the attached picture. T - time, N - number of channels. As you can see, there is a maximum of 4 occupied channels between T6B and T2E. In principle, there can be several such maximum values. I have some basic ideas how to start working on this, вut I am sure that this is a well-known problem that has a solution in the form of a proven algorithm.

Answer 1

You are right it is indeed a common problem. You can state it this way: Given an array of segments find a maximum number of intersecting segments.

Intuition

Basically, you can look at your image. Declare cumulative variable, then go form left to right, any time the call is started you add one, when the call is ended you substract one. All time maximum value of variable is the answer.

Algorithm

Let segments be an array of pairs (start, end) of length N.

Construct array events of pairs (time, event), where

• time equals to all possible start and end from segments;
• event equals to 1 if time is a start of any segment and -1 if it is an end.

Sort array events in ascending order.

Let cur = 0 be a cumulative variable.
Let mmax = 0 be a maximum number of intersecting segments.

Iterate over array events and on every iteration:

1. Add current value to cur
2. Set mmax to maximum between mmax and cur

max is an answer.

Different solutions.

Note

You should properly handle situations when in any given moment one call is ending and another one is starting (which event comes first?).