욕심 많은 알고리즘을위한 최적 알고리즘 : 간격 스케줄링 - 모든 간격 예약

Question

최근에 Tardos 및 Kleinberg의 알고리즘 디자인 4 장에있는 간격 스케줄링 알고리즘에 대해 읽었습니다. 간격 일정 문제로 제공하는 솔루션이이었다 :

C++/자바/파이썬에서이 알고리즘은 여기에서 찾을 수 있습니다

Sort the n intervals based on their finishing time and store in array F 
A = [] #list of intervals 
S = array with property that S[i] contains the finishing time of the ith interval 
i = 0 
For j = 0 to n-1 
    if S[j] >= F[i] #this interval does not overlap with the ith interval 
     i = j 
     A.add(j) 

: http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/

또한 간격 색칠 문제로 알려진 문제의 확장, 다음과 같이 설명 할 수있다.

는 우리는 간격 세트를 제공, 우리는 간격이 같은 색이 교차하지 않는 부여 및 목표 가 사용되는 색상의 수를 최소화하는 것입니다 있도록 모든 간격 색상 할 수 있습니다.

Sort the intervals by their start times in a list I 
n = len(I) 
For j = 1 to n: 
    For each interval I[i] that precedes I[j] and overlaps it: 
     Exclude the label of I[i] from consideration for I[j] 
The jth interval is assigned a nonexcluded label 

그러나이 알고리즘의 실행 시간 O (N^2)되지 않습니다 :이 책에서 제안

알고리즘이 있었다? 나는 더 나은 것을 생각했지만 그것이 맞는지 확실하지 않습니다. 기본적으로 Interval Scheduling 알고리즘을 수정합니다.

Sort the n intervals based on their finishing time and store in array F 
A = [] 
x = 1 
S = array with property that S[i] contains the finishing time of the ith interval 
i = 0 
while F is not empty: 
    new = [] 
    For j = 0 to n-1 
     if S[j] >= F[i] #this interval does not overlap with the ith interval 
      i = j 
      A.add(F[j]) 
     else: 
      new.add(F[j]) 
    F = new 
    Recompute S 
    print x, A 
    A = [] 
    x++ 

의사 코드에 어리석은 버그가있을 수 있지만 알고리즘이 무엇을하는지 이해하시기 바랍니다. 기본적으로 나는 표준 간격 스케줄링 알고리즘을 반복적으로 실행하여 가능한 모든 색상을 떼어 낼 것입니다.

내 알고리즘이 간격의 다양한 색상을 모두 인쇄하지 않아야합니까? 이 알고리즘이 올바른 알고리즘이라면 이전 알고리즘보다 효율적입니까? 그렇지 않은 경우, 반대 사례를 제공해 주시겠습니까? 감사합니다. (간격 스케쥴에 대한 자세한 내용은 여기 : https://en.wikipedia.org/wiki/Interval_scheduling)

Answer 1

알고리즘이 차선책을 생성 할 수 있습니다. 분명히

---  ----- 
    ---- 
    ------------ 

다음 2 색 용액 (검증 최적 알고리즘에 의해 생성 될) 동일한 입력 가능하다 : 여기에서, 알고리즘이 생성 될지의 예

--- ------------ 
    ---- ----- 

마지막으로 O (n^2) 시간이 필요한 것처럼 책의 제안 된 알고리즘에 대한 의사 코드 설명이 실제로 보이지만 다른 데이터 구조를 사용하여 속도를 높일 수 있습니다. 다음은 O (n log n) 알고리즘입니다. 모든 n 간격을 반복하여 루프하는 대신 모든 2n 간격 끝점을 순서대로 반복하십시오. 색상별로 정렬 된 사용 가능한 색상의 힙 (우선 순위 대기열)을 유지합니다. 처음에는 n 색상이 포함되어 있습니다. 간격 시작점이 나타날 때마다 힙에서 가장 작은 색상을 추출하여이 간격에 할당합니다. 간격 끝점을 볼 때마다 지정된 색상을 힙에 다시 삽입하십시오. 처리되는 각 종점 (시작 또는 끝)은 O (log n) 시간이고, 2n 개입니다. 이것은 간격을 정렬하기위한 시간 복잡성과 일치하므로 전체 시간 복잡도도 O (n log n)입니다.