更快的计算活动呼叫的算法

Question

我们正在为呼叫中心实施密度报告.结果必须显示为表格,每天一行显示当天同时活动的最大呼叫数.

我们正在构建UI背后的lib.合同指定我们接收当天的呼叫数和两个整数数组,一个具有开始时间,另一个具有每个呼叫的结束时间,因此,例如:

对于给定的一天,只收到两个呼叫:一个从时间20到30,另一个从10到20.同时呼叫的最大数量是1.

另一方面,另一天,还收到两个呼叫,一个从10到45,另一个从15到40,然后最大同时呼叫数是2.

Web服务的合同就是这样

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

数据看起来像这样(假设那天收到了3个电话).第一个从10到25,第二个从12到30,第三个从20到23.

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

回报必须是:3.

我已经实现了这个解决方案:

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;
}

当呼叫次数达到1000次(周末)时,它的效果很好,但在工作日内,数量非常大,计算时间也很长(> 5分钟).我现在原因可能是我的解决方案是使用两个嵌套循环,但我没有很多复杂算法的经验所以我的问题是:

鉴于我只需要同时调用的最大数量(不是时间和调用者),如果有的话,这可能是执行此计算的更快方法.

Answer 1

随着N的增长,你的时间会迅速增长(N*N).一个简单的解决方案(如果你的时间是午夜过了几分钟)将创建一个1440个整数的数组,其中包含当天每分钟的通话数变化.然后,您只需从0循环一次到N-1,并且对于每个元素,通过在呼叫开始时递增值并在结束时递减来调整该时间点的呼叫计数增量的计数.之后,只需查看计数即可获得最大值.对于较大的N值,这应该快得多.

由于1440是常数(对于最后一步),并且输入不需要进行排序,因此这应该具有线性时间复杂度.此算法的运行时间不受平均调用长度的影响.

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;        
}

对于比较,N = 50,000并且随机呼叫长度在1到40分钟之间,问题中的算法使用29,043毫秒,并且该算法使用8毫秒.我在c#中运行这些测试,但它们应该与Java产生的相当.