가장 큰 합계 가중치의 합계 가중치가 가장 큰 간격을 찾는 알고리즘

Question

글쎄, 설명하기가 어렵다고 생각한다.

우리는이 그림에서 볼 수 있듯이

은, 시간의 6 개 간격이있다. 각각 무게가 있습니다. 불투명도가 높을수록 무게가 커집니다. 가장 큰 합계 가중치로 간격을 찾는 알고리즘을 원합니다. 그림의 경우 가장 높은 불투명도의 영역 인 간격 5와 6의 겹침이됩니다.

Answer 1

• 각 간격을 시작점과 끝점으로 나눕니다.

• 포인트를 정렬하십시오. 사용하여 포인트를 통해 0

• 반복 처리의 합과

• 시작합니다 sweep-line algorithm :

  • 당신은 시작 지점 얻을 경우

    • 에 의해 합계를 증가를 대응하는 간격의 값

    • 합계 수가 지금까지 가장 좋은 합계보다 높으면이 시작점을 저장하고 플래그를 설정하십시오. 당신이 끝 지점 얻을 경우

  • 는 : 플래그가 설정되어있는 경우

    • 을, 지금까지 저장된 시작점과 최적의 간격과 현재의 합이 끝점을 저장하고를 재설정 깃발.

    • 해당 간격 값만큼 카운트를 줄입니다.

  이 오버랩 구간의 최대 개수보다는 최대 합산 중량을 찾는 즉 가중 된 버전에 기초 the answer I wrote here,에서 유래

.

예 :이 예

:로

시작/끝 지점

정렬한다 : (시작 S = E = 단부)

1S, 1E, 2S, 3S, 2E, 3E, 4S, 5S, 4E, 6S, 5E, 6E 

이들을 반복하면서 플래그를에 설정합니다., 5S 및 6S이며 각각의 간격은 1E, 4E 및 5E (위의 시작 지점 이후 첫 번째 끝점 임)에 저장합니다.

2S, 3S 또는 4S에 플래그를 설정하지 마십시오. 합계는 지금까지의 최고 합보다 낮습니다.

Answer 2

알고리즘 논리는 그림에서 파생 될 수 있습니다. 시간 간격의 분해가 1 분이라고 가정하면, 배열이 생성되어 모든 계산에 사용될 수 있습니다.

1. 24 * 60 요소의 배열을 만들고 0 가중치로 채 웁니다.
2. 각 시간 간격에 대해이 간격의 가중치를 배열의 해당 부분에 더하십시오.
3. 배열을 반복하여 최대 합계 가중치를 찾습니다.
4. 다시 배열을 반복하고 최대 합계 가중치를 사용하여 배열 인덱스 (시간)를 출력합니다.

출력에 간격 인덱스가 있어야하는 경우이 알고리즘은 약간 다른 작업으로 수정할 수 있습니다. 이 경우 배열에는 입력 시간 간격 인덱스의 목록이 두 번째 차원으로 포함되어야합니다 (또는 특정 언어에 따라 별도의 배열이 될 수 있음).

UPD. 이 간단한 알고리즘이 @Dukeling에서 제안한 것보다 훨씬 더 느리다면 궁금합니다. 두 알고리즘을 모두 코딩하고 입력 생성기를 만들어 성능을 평가했습니다.

발생기 :

#!/bin/sh 
awk -v n=$1 ' 
BEGIN { 
    tmax = 24 * 60; wmax = 100; 
    for (i = 0; i < n; i++) { 
    t1 = int(rand() * tmax); 
    t2 = int(rand() * tmax); 
    w = int(rand() * wmax); 
    if (t2 >= t1) {print t1, t2, w} else {print t2, t1, w} 
    } 
}' | sort -n > i.txt 

알고리즘 1 :

#!/bin/sh 
awk ' 
{t1[++i] = $1; t2[i] = $2; w[i] = $3} 
END { 
    for (i in t1) { 
    for (t = t1[i]; t <= t2[i]; t++) { 
     W[t] += w[i]; 
    } 
    } 
    Wmax = 0.; 
    for (t in W){ 
    if (W[t] > Wmax) {Wmax = W[t]} 
    } 
    print Wmax; 
    for (t in W){ 
    if (W[t] == Wmax) {print t} 
    } 
} 
' i.txt > a1.txt 

알고리즘 2 :

#!/bin/sh 
awk ' 
{t1[++i] = $1; t2[i] = $2; w[i] = $3} 
END { 
    for (i in t1) { 
    p[t1[i] "a" i] = i "S"; 
    p[t2[i] "b" i] = i "E"; 
    } 
    n = asorti(p, psorted, "@ind_num_asc"); 
    W = 0.; Wmax = 0.; f = 0; 
    for (i = 1; i <= n; i++){ 
    P = p[psorted[i] ]; 
    k = int(P); 
    if (index(P, "S") > 0) { 
     W += w[k]; 
     if (W > Wmax) { 
     f = 1; 
     Wmax = W; 
     to1 = t1[k] 
     } 
    } 
    else { 
     if (f != 0) { 
     to2 = t2[k]; 
     f = 0 
     } 
     W -= w[k]; 
    } 
    } 
    print Wmax, to1 "-" to2 
} 
' i.txt > a2.txt 

결과

$ ./gen.sh 1000 
$ time ./a1.sh 
real 0m0.283s 
$ time ./a2.sh 
real 0m0.019s 
$ cat a1.txt 
24618 
757 
$ cat a2.txt 
24618 757-757 
$ ./gen.sh 10000 
$ time ./a1.sh 
real 0m3.026s 
$ time ./a2.sh 
real 0m0.144s 
$ cat a1.txt 
252452 
746 
$ cat a2.txt 
252452 746-746 
$ ./gen.sh 100000 
$ time ./a1.sh 
real 0m34.127s 
$ time ./a2.sh 
real 0m1.999s 
$ cat a1.txt 
2484719 
714 
$ cat a2.txt 
2484719 714-714 

간단히 ~ 20x 느립니다.