친구가 O (n^3) 시간보다 더 잘 해결할 수 있다고 말한 퍼즐을 나에게주었습니다.가장 겹치는 오버랩 작업 찾기
각각 시작 시간과 종료 시간이 설정된 n 개의 작업 집합 (매우 겹치는 부분)이 있으면 모든 작업에 해당 작업이 포함되거나 해당 작업과 겹치는 작업을 포함하는 가장 작은 하위 집합을 찾습니다.
최적의 솔루션은 가장 겹쳐져 있지 않은 겹쳐진 부분을 선택하여 솔루션 세트에 추가 한 다음 표시하고 겹치는 것입니다. 모든 작업이 표시 될 때까지 반복하십시오.
가 알아내는하는 일,이가 O을, 자국을 업데이트하기 위해, 작업이 선택 될 때마다 다시 수행한다 (N- (N^2) (O) 간단한 인접 행렬을 가장 도장이 overlappers이다 갖는다^3).
더 좋은 솔루션이 있습니까?
A을 아직 겹치지 않은 작업 집합이라고합시다.
t)가 A에서 작업 x을 찾습니다.t보다 작은 모든 작업에서 : 최대 종료 시간 인 j을 선택하십시오.j을 출력 세트에 추가하십시오.j과 중복되는 모든 작업을 A에서 제거하십시오.간단한 구현에서 실행 O (N은 2 ^). interval trees 사용은 (n 개의 *의 logn) O에 해결하기 위해 아마 가능합니다.
최적의 솔루션 (공식적인 증거가 아닌)의 기본 개념 : 시작 시간이 t보다 작은 하나의 작업을 선택해야 x이 겹쳐집니다. S을 시작 시간이 t 미만인 모든 작업 세트로 설정하면 j이 S에있는 작업과 동일한 작업과 중복되는 것으로 나타날 수 있습니다. S에서 하나의 직업을 골라야하기 때문에 최선의 선택은 j입니다. 우리는이 아이디어를 사용하여 일자리 수를 유도함으로써 증거를 만들 수 있습니다.
이 알고리즘은 {[0,2], [1,4], [3,10], [5,6], [7,8]} (예 : [이 질문] : //stackoverflow.com/q/26170904/535871)). {[1, 4], [5,6], [7,8]}을 생성하는 반면, {[0,2], [3,10]}과 {[1, 4], [3, 10]}. –
@TedHopp 알고리즘이 올바르게 작동합니다. 집합 {[1,4], [3,10]}을 생성합니다. 2 단계에서 A에 있지 않더라도 모든 작업을 선택할 수 있습니다. – interjay
우리는 동적 프로그래밍 방식으로 O (nlogn) 솔루션을 얻을 수 있습니다. 특히 k 작업 작업을 포함하여 가장 작은 세트의 크기를 고려하고 S(k)으로 표시되는 첫 번째 k 작업 (시작 시간 순서)과 일치시키는 것이 좋습니다. 보조 작업 (∞, ∞)을 먼저 추가해야합니다. 결과는이 최종 작업에 대한 DP 솔루션에서 1을 뺀 것입니다.
S(k)을 계산하려면 작업 p(k)이 작업 k보다 먼저 종료되지만 최대 시작 시간을 갖는 것으로 간주하십시오. p은 증가하는 기능입니다. S(k)은 최소 S(i)과 end(i) > start(p(k)) 중 하나가됩니다.
잠재적 작업의 힙 (S(k))을 유지함으로써이 작업을 효율적으로 찾을 수 있습니다. 각 S(k)을 계산 한 후, 우리는 힙에 작업을 추가합니다.우리가 일자리를 얻고 자 할 때, 우리는 적절한시기가 오기까지 너무 일찍 끝나는 힙 바닥에서 일자리를 제거합니다. 우리가 각 힙 연산 (pop/peek/push)의 O (n)을 최대로 수행하기 때문에 이것은 최대로 O (nlogn)의 총계를 취할 것입니다.
나머지 작업은 p(k) 값을 효율적으로 계산하는 것입니다. 이 작업을 수행하는 한 가지 방법은 모든 작업 시작과 끝 (반복되는 작업 시간)을 반복하여 최신 시작 작업을 추적하는 것입니다.
당신의 솔루션은 탐욕스럽고 언제나 사실이 아니며 (나는 실패한 사례를 줄 수 있음), 더 나은 복잡성으로 구현 될 수도 있습니다. –
@izomorphius 그것은 욕심이 많다. 그러나 나는 그것이 최적이 아닌 것을 증명할 수 없었다. 어떤 아이디어가 더 나은 복잡성을 가진 솔루션입니까? – kwiqsilver
나는 탐욕 스럽지만 그것이 정확하지 않다는 것을 안다. 예 : 간격 : (0, 2), (1, 4), (3,6), (5,8), (7, 10). 첫 번째 단계 간격 (1,4), (3,6), (5,8) 모두 두 가지를 모두 포함하므로 둘 중 하나를 선택할 수 있지만 가장 좋은 대답은 (1,4) 및 (5)를 선택하면됩니다. , 8). 대부분의 간격을 포함하는 간격이 고유하게 식별되는 예가 있지만 여전히 최상의 솔루션에는 포함되지 않지만 생각하기가 조금 더 어렵습니다. 당신이 주장한다면 나는 하나를 주려고 노력할 것입니다. –