Question

我们正在对呼叫中心进行密度报告。结果必须显示为表格, 每天以一行显示该天最大“ 强” 同时 < 强” / 强” 活动电话数。

我们正在UI背后建立lib。合同具体规定了当天的通话次数和两个整数阵列, 一个是起始时间, 一个是每次通话的结束时间, 例如 :

一天只接到两个电话:一个从20到30,另一个从10到20,同时拨打最多为1次。

另一方面,另外一天还收到两通电话,一通从10通到45通,另一通从15通到40通,然后最多同时接到2通。

网络服务合同是这个

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次(周末),但工作日内,这个数目相当大,计算得那么长( & gt; 5 分钟), 这非常管用。现在原因可能是我的解决方案是用两个嵌套周期,但我对复杂的算法没有多少经验,所以我的问题是:

鉴于我只需要同时打电话的最多次数(而不是时间和打电话者),如果有的话,这可以是一个更快的计算方法。

Answer 1

随着时间的迅速增长(N*N),一个简单的解决方案(如果时间是午夜前的间隔时间)是创建1 440 英寸的阵列,该阵列将包含每天每一分钟的调用计数的变化。然后,您可以从 0 到 N-1 圈一次,然后对每个元素循环一次,在那个时刻调整调用计数 delta 的计数,方法是在调用开始时加增数值,并在停用时减缩。然后,通过计数来获取最大的值。对于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 的产物相似。

Answer 2

请允许我提出另一种算法。鉴于最多为24*60 = 1440 分钟, 为何不设置直方图阵列来计算每分钟同时通话的次数。

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

复杂程度是 O( m*n), m 是通话的平均长度。因为通话次数可能超过1000次, 所以如果运气好的话, 这个算法在实际中会更快。

Answer 3

你的算法非常慢因为它实际上测试了所有可能的病例也就是O(n)2

Assuming that your calls are ordered when you receive them, here is an 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;
  }

[强注 < 强注 < / 强: 此代码极有可能将阵列索引从射程错误中丢出, 但应该足以显示这个想法, 以便您可以执行其余的]

如果电话未分类,算法为O(n lg n):

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

在开始时间排序所有调用。通过列表循环, 并保留一个“ 激活调用” 列表, 在结束时间排序。应该与此类似 :

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

运行时间应该是 O(nlog n)

P.S.:如果我们能够假定在开始时间之前已经发出电话订单,就应有可能简化这一程序。

Answer 5

调用事件阵列。调用事件只是一个带有时间字段和起始字段的结构,其值为+1或 -1,用于调用开始和调用结束。调用事件开始之前按时间字段对这个阵列进行排序(如果时间相等,然后使用第二个字段,结束事件开始之前) 。初始化当前Calls = 0。迭代数组,将 StartEnd 字段添加到当前Calls。在数组扫描过程中,需要使用当前Calls 的最大值。

Answer 6

开始时间排序您的持续时间。这样, 当您内部循环的起始时间超出外部循环所提供的范围时, 您就可以使用内部循环 < code> break 。

Answer 7

使用两个列表, 在列表中添加 X(i) Y(i) 配对。第一个列表在调用开始时间排序, 第二个列表在结束时间排序。在列表中循环仅跳过最低时间列表。

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

友情链接