활성 통화 계산을위한보다 빠른 알고리즘

Question

콜 센터에 대한 밀도 보고서를 구현하고 있습니다. 결과는 해당 일 동안 동시 전화 동시 통화의 최대 수를 보여주는 일일 행 테이블로 표시되어야합니다.

우리는 UI 뒤에 lib를 만들고 있습니다. 계약서는 해당 날의 호출 수와 두 개의 정수 배열을 받도록 지정합니다. 하나는 시작 시간이고 다른 하나는 각 호출의 종료 시간입니다. 예를 들면 다음과 같습니다.

주어진 날 동안 두 번의 호출이 있습니다. 수신 : 하나는 시간 20에서 30으로 가고 다른 하나는 10에서 20으로 이동합니다. 동시에 최대 통화 수는 1입니다.

한편 다른 날에는 2 회, 10 회에서 45 회까지 수신됩니다 및 15 내지 40에서 다른 호출은 동시에 최대 개수는 웹 서비스 계약이

.

이다

데이터가 다음과 같이 표시됩니다 (해당 날짜에 3 번 통화 한 경우). 10에서 25로 먼저 하나, 30-12에서 두 번째 23

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

그리고 20 ~ 세번째는 반환해야합니다 :

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

통화 수가 최대 1,000 회 (주말)이지만 근무일 내에 전화 번호가 꽤 크고 계산 시간이 오래 걸립니다 (5 분 초과). 이제는 내 솔루션이 두 개의 중첩 된 사이클을 사용하고있는 것일 수 있지만 복잡한 알고리즘에 대한 경험이 거의 없기 때문에 질문에 답할 수 있습니다.

최대 동시 호출 수 (시간도 호출자)이 있으면이 계산을 수행하는 더 빠른 방법이 될 수 있습니다.

Answer 1

N이 커지면 빠르게 성장합니다 (N * N). 간단한 해결책 (시간이 자정 넘은 분 간격 인 경우)은 하루 동안 매분마다 호출 수가 변경되는 1440 int 배열을 만드는 것입니다. 그런 다음 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 = 5 1 분에서 40 분 사이의 임의의 호 길이와 상기 해당 알고리즘은 29,043 밀리 사용하고,이 알고리즘은 8 밀리 초를 사용 하였다. 나는이 테스트를 C#에서 실행했지만 Java가 생성하는 것과 비교할 수 있어야합니다.

Answer 2

두 개의 목록을 사용하여 해당 목록에 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--; 
    } 
} 

Answer 3

통화 이벤트 배열을 만듭니다. 호출 이벤트는 호출 시작 및 호출 종료에 대한 값이 +1 또는 -1 인 시간 필드 및 시작 필드가있는 구조입니다. 이 배열을 시간 필드별로 정렬하십시오 (시간이 동일하면 두 번째 필드를 사용하고 시작 이벤트 전에 종료 이벤트 사용). CurrentCalls = 0 초기화. 배열을 반복하고 StartEnd 필드를 CurrentCalls에 추가합니다. 배열 스캐닝 중 CurrentCalls의 최대 값이 필요합니다.

Answer 4

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)이 알고리즘이다

: 가능성이 던져 배열 범위 오류 중 인덱스,하지만 전화가 정렬되지 않는 경우]

을 나머지를 구현할 수 있도록 아이디어를 보여 충분해야한다는 알고리즘 (N LG 전자 N) O입니다

Answer 5

다른 알고리즘을 제안 해주세요. 주어진 시간이 최대 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 6

시작 시간별로 기간을 정렬하십시오. 이렇게하면 내부 루프의 시작 시간이 외부 루프에 의해 제공되는 범위를 벗어날 때 break 내부 루프를 수행 할 수 있습니다.

Answer 7

모든 통화를 시작 시간순으로 정렬하십시오. 목록을 반복하고 "활성 통화"목록을 종료 시간순으로 정렬하십시오. 이 유사하게 나타납니다

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를

P.S을 (N 로그 n) : 우리가 호출이 이미 시작 시간으로 정렬한다고 가정 할 경우이를 단순화 할 수 있어야한다.