4

コールセンターの密度レポートを実装しています。結果は、その日の同時アクティブコールの最大数を示す1日あたりの行を含むテーブルとして表示する必要があります。

UIの背後にライブラリを構築しています。コントラクトは、その日の呼び出しの数と整数の2つの配列を受け取ることを指定しています。1つは各呼び出しの開始時刻と終了時刻です。たとえば、次のようになります。

特定の日に受信されるコールは2つだけです。1つは時間20から30に、もう1つは10から20になります。同時にコールする最大数は1です。

一方、別の日には、10から45までと15から40までの2つのコールも受信され、同時にコールされる最大数は2です。

Webサービスの契約はこちらです

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

そして、データは次のようになります（その日に受信した3つの呼び出しを想定しています）。1つ目は10から25、2つ目は12から30、3つ目は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分）。私の解決策は2つのネストされたサイクルを使用しているためかもしれませんが、複雑なアルゴリズムの経験があまりないので、私の質問は次のとおりです。

同時に呼び出す最大数（時間や呼び出し元ではない）が必要な場合は、この計算を実行するためのより高速な方法である可能性があります。

4

7 に答える 7

5

Nが大きくなると、時間も急速に長くなります（N * N）。簡単な解決策（時間が深夜0時過ぎの分間隔の場合）は、1日の1分ごとの呼び出し数の変化を含む1440intの配列を作成することです。次に、0からN-1まで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が生成するものと同等である必要があります。

于 2012-05-23T19:08:32.220 に答える
2

別のアルゴリズムを提案させてください。1日あたり最大24*60 = 1440分であるとすると、ヒストグラム配列を作成して、1分あたりの同時呼び出し数を計算してみませんか。

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をはるかに超える可能性があるため、運が良ければ、このアルゴリズムは実際にはより高速になります。

于 2012-05-23T19:25:38.210 に答える
1

O（n ^ 2）であるすべての可能なケースを文字通りテストするため、アルゴリズムは非常に低速です。

呼び出しが受信時に順序付けられていると仮定すると、O（n）アルゴリズムは次のようになります。[編集：2番目の配列を並べ替える必要があります]

    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;
于 2012-05-23T19:12:54.130 に答える
1

すべての通話を開始時刻で並べ替えます。リストを繰り返し処理し、終了時刻でソートされた「アクティブコール」リストを保持します。これに似ているはずです：

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（n log n）である必要があります

PS：呼び出しがすでに開始時刻で順序付けられていると想定できる場合は、これを単純化できるはずです。

于 2012-05-23T19:43:29.170 に答える
0

2つのリストを使用し、それらのリストにX [i]Y[i]ペアを追加します。最初のリストは通話の開始時刻で並べ替えられ、2番目のリストは終了時刻で並べ替えられます。最も低い時間リストのみをステップ実行して、リストを繰り返し処理します。

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--;
    }
}
于 2012-05-23T19:09:44.513 に答える
0

呼び出しイベントの配列を作成します。呼び出しイベントは、呼び出しの開始と呼び出しの終了に値+1または-1の時間フィールドと開始フィールドを持つ単なる構造です。この配列を時間フィールドで並べ替えます（時間が等しい場合は、2番目のフィールドである開始イベントの前に終了イベントを使用します）。CurrentCalls = 0を初期化します。配列を繰り返し、StartEndフィールドをCurrentCallsに追加します。配列スキャン中のCurrentCallsの最大値が必要です。

于 2012-05-23T19:10:42.937 に答える
0

開始時間で期間を並べ替えます。そうすれば、内側のループの開始時間が外側のループによって提供される範囲外になったときに、内側のループを実行できbreakます。

于 2012-05-23T19:35:06.757 に答える