Faster algorithm for counting active calls

Question

We run a density report for a call center. The result should be displayed as a table with a row per day, showing the maximum number of active calls simultaneously during this day.

We create lib behind the interface. The contract indicates that we get the number of calls for that day and two arrays of integers, one with the start time and one with the end time of each call, therefore, for example:

During this day, only two calls are accepted: one goes from 20 to 30, and the other from 10 to 20. The maximum number of simultaneous calls is 1.

On the other hand, during another day, two calls are also accepted, one from 10 to 45, and the other from 15 to 40, then the maximum number of simultaneous calls is 2.

The contract for the web service is

public static int GetMaxDensity(int N, int[] X, int[] Y) 

And the data looks like this (suppose 3 calls that were received that day). First one from 10 to 25, the second from 12 to 30 and the third from 20 to 23.

 N = 3, X = {10, 12, 20} Y = {25, 30, 23} 

And the return should be: 3.

I implemented this solution:

 public static int GetMaxDensity(int N, int[] X, int[] Y) { int result = 0; for (int i = 0; i < N; i++) { int count = 0, t = X[i]; for (int j = 0; j < N; j++) { if (X[j] <= t && t < Y[j]) count++; } result = Math.max(count, result); } return result; } 

And it works great when the number of calls reaches 1000 (weekends), but on working days the number is quite large, and the calculation takes so long (> 5 minutes). Now I can explain that I use two nested loops, but I don't have much experience with complex algorithms, so my question is:

Given that I just need the maximum number of simultaneous calls (not time and not calling), which may be a faster way to perform this calculation, if any.

Answer 1

As N grows, your time grows rapidly (N * N). A simple solution (if your time is in the intervals of minutes past midnight) would be to create an array of 1440 ints that would contain a change in the number of calls per minute during the day. Then you can scroll once from 0 to N-1, and for each element, set the counter of the delta of the call delta at this point in time, increasing the value at the time the call starts and decreasing it at the end time. After that, just look at the counters to get the highest value. This should be much faster with large N.

Since 1440 is a constant (for the last step), and the inputs do not need to be sorted, this should have linear time complexity. The average duration of a call to this algorithm is independent of execution time.

 public static int GetMaxDensity(int N, int[] X, int[] Y) { int rangeStart = Integer.MAX_VALUE; int rangeEnd = Integer.MIN_VALUE; for(int i=0; i<N; i++) { if (X[i] < rangeStart) rangeStart = X[i]; if (Y[i] > rangeEnd) rangeEnd = Y[i]; } int rangeSize = rangeEnd - rangeStart + 1; int[] histogram = new int[rangeSize]; for (int t = 0; t < rangeSize; t++) histogram[t] = 0; for (int i = 0; i < N; i++) { histogram[X[i]-rangeStart]++; histogram[Y[i]-rangeStart]--; } int maxCount = 0; int count = 0; for (int t = 0; t < rangeSize; t++) { count += histogram[t]; if (count > maxCount) maxCount = count; } return maxCount; } 

For comparison: at N = 50,000 and random call lengths between 1 and 40 minutes, the algorithm in question used 29,043 milliseconds, and this algorithm used 8 milliseconds. I conducted these tests in C #, but they should be comparable to what Java will produce.

Answer 2

Let me suggest a different algorithm. Given that there is a maximum of 24 * 60 = 1440 minutes, why not make an array of histograms to calculate the number of simultaneous calls per minute.

 public static int GetMaxDensity(int N, int[] X, int[] Y) { int[] h = new int[1440]; // loop through all calls for (int i=0; i<N ; i++){ addIt(X[i], Y[i], h); } // find max int m = 0; for(int i =0 ; i<1440; i++){ if (h[i]>m) m = h[i]; } return m; } // counting for one call public static void addIt(int x, int y, int[] h){ for ( int i=x;i<y;i++){ h[i]++; } } 

Difficulty - O (m * n), where m is the average call length. Since the number of calls can be much more than 1000, so, with some luck, this algorithm will be faster in practice.

Answer 3

Your algorithm is very slow because it literally checks for all possible cases, which is O (n ^ 2).

Assuming your calls are ordered when you receive them, here is the O (n) algorithm: [EDIT: second array should be sorted]

  int max; int i=0,j=0,count=0; while(i<n && j<n){ if(x[i]<y[j]){ //new call received count++; max = count>max? count:max; i++; }else if(x[i]==x[j]){ //receive new call at the same time of end call i++; j++; }else { //call ended count--; j++; } } return max; } 

[ note : this code is most likely to throw an array index error out of range, but should be good enough to demonstrate the idea so you can implement the rest]

if calls are not sorted, O (n lg n) algorithm:

 array_of_calldata a = x union y a.sort(); foreach(calldata d in a){ if (d is new call) count++; else count--; } return max_value_of_count; 

Answer 4

Sort all calls by start time. Scroll through the list and save the list of “active calls” sorted by end time. It should look something like this:

 public class DensityReport { static int count; static class Call { public Call(int x, int y) { double f = 0.1/(++count); start = x + f; end = y + f; } double start; double end; } public static int getMaxDensity(int n, int[] x, int[] y) { // Calls sorted by start time TreeSet<Call> calls = new TreeSet<Call>(new Comparator<Call>() { public int compare(Call c1, Call c2) { return c1.start < c2.start ? -1 : c1.start > c2.start ? 1 : 0; } }); // Add all calls to the sorted set. for (int i = 0; i < n; i++) { calls.add(new Call(x[i], y[i])); } int max = 0; // Active calls sorted by end time TreeSet<Call> activeCalls = new TreeSet<Call>(new Comparator<Call>() { public int compare(Call c1, Call c2) { return c1.end < c2.end ? -1 : c1.end > c2.end ? 1 : 0; } }); for (Call call: calls) { // Remove all calls that end before the current call starts. while(activeCalls.size() > 0 && activeCalls.first().end < call.start) { activeCalls.pollFirst(); } activeCalls.add(call); if (activeCalls.size() > max) { max = activeCalls.size(); } } return max; } } 

Runtime should be O (n log n)

PS: It should be possible to simplify if we can assume that the calls are ordered by start time.

Answer 5

Use two lists, add X [i] Y [i] pairs to these lists. The first list is sorted by the start time of the call, the second - by the end. Go through the lists only by selecting the lowest time list.

 class Call { int start; int end; } Call callsSortedOnStart[]; Call callsSortedOnEnd[]; int indexStart = 0; // Position in the array int indexEnd = 0; int nCalls = 0; // Current density of calls int maxCalls = 0; // Maximum density of calls while(indexStart < callsSortedOnStart.length && indexEnd < callsSortedOnEnd.length) { while(callsSortedOnStart[indexStart].start <= callsSortedOnEnd[indexEnd].end) { indexStart++; nCalls++; } maxCalls = max(maxCalls, nCalls); while(callsSortedOnStart[indexStart].start > callsSortedOnEnd[indexEnd].end) { indexEnd++; nCalls--; } } 

Answer 6

Make an array of call events. A call event is just a structure with a time field and a start field with a value of +1 or -1 to start and end a call. Sort this array by time (if times are equal, then use the second field, end of event before event starts). Initialize CurrentCalls = 0. Iterate the array, add the StartEnd field to CurrentCalls. The maximum value of CurrentCalls during array scanning is what you need.

Answer 7

Sort the time by start time. That way, when the start time in your inner loop goes beyond the range provided by your outer loop, you can break inner loop.