java - 计算 Activity 调用的更快算法

Question

我们正在为调用中心实现密度报告。结果必须以表格的形式显示，每天一行显示当天同时 Activity 调用的最大数量。

我们正在构建 UI 背后的库。契约(Contract)指定我们收到当天的通话次数和两个整数数组，一个是开始时间，一个是每次通话的结束时间，例如:

对于给定的一天，只收到两个电话:一个从时间 20 到 30，另一个从 10 到 20。同时调用的最大数量是 1。

另一方面，另一天，也接到两个电话，一个从 10 到 45，另一个从 15 到 40，那么同时调用的最大数量是 2。

Web 服务的契约(Contract)是这样的

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 产生的结果相当。