가장 큰 합계 값을 갖는 간격 그룹을 선택하는 알고리즘

Question

가능한 한 효과적인 방법 (아마도 선형 복잡성)으로 다음 문제를 어떻게 해결할 수 있습니까?

입력 값으로, 값 (정수)을 보유하는 간격 (시작, 끝)이 있습니다. 간격은 고정되어 있지 않습니다. 겹치지 않는 간격의 그룹을 찾고 그 값의 합이 가능한 가장 높습니다 (따라서 간격의 수는 결과 값만큼 중요하지 않음).

평가 된 가장자리가있는 그래프로 구현하고 아마도 Djikstra 또는 비슷한 것을 사용하려고 생각했습니다. 그러나 문제는 너무 많은 시간이 걸리는 그래프에 삽입하는 것입니다. 이 방법으로 그래프를 효과적으로 만들 수 있습니까?

Answer 1

시작과 관련하여 간격을 정렬하여 시작하십시오. i 이상의 모든 간격을 고려하여 최대 합계를 제공하는 함수 f(i)을 정의하십시오. 이 기능은 동적 프로그램으로 계산할 수 있습니다.

1. 이 i을 포함하고 있으므로, i 겹치지 않는 다음 간격으로 계속 : f(i)를 지정하려면이 옵션을
   i.value + f(nextNonOverlappingInterval)
2. i을 포함하고 다음 간격으로 계속하지 마십시오 :
   를 f(nextInterval)

그래서 전반적으로, 함수는 다음과 같습니다

,536,

f(i) = max(i.value + f(nextNonOverlappingInterval), f(nextInterval)) 

동적 인 프로그램을 설정하여 마지막 간격에서 시작하여 f을 계산하고 첫 번째 메시지에 전파 한 다음 솔루션을 얻습니다.

앞뒤로 계산하거나 메모를 사용하여 문제를 해결하기 위해이 문제의 대안 공식을 사용할 수도 있습니다.

Answer 2

이 문제는 가중치 간격 예약으로 알려져 있습니다.

아이디어는 오른쪽 끝을 기준으로 간격을 정렬 한 다음 동적 프로그래밍을 사용하여 특정 간격으로 끝나는 가장 무거운 부분 집합의 가중치를 찾습니다. 이진 검색을 사용하면 현재 가장 효율적인 간격보다 먼저 선택할 수있는 가장 엄한 간격을 찾을 수 있습니다. 시간 복잡도는 O(N log N)입니다.

자세한 내용은 https://courses.cs.washington.edu/courses/cse521/13wi/slides/06dp-sched.pdf에서 확인할 수 있습니다.