겹침이 없도록 제거하는 최소 횟수

겹치는 구간들이 있을 때 더 이상 서로 겹치지 않도록 최소한의 제거를 수행하려고 합니다. 가능한 한 많이 남겨 두십시오. ✂️

최소한으로 제거하는 것은 겹치지 않는 구간을 최대한 많이 유지하는 것과 같습니다. 유지하는 문제를 해결한 뒤, 제거 횟수는 n에서 유지한 개수를 뺀 값으로 구합니다.

겹치지 않는 구간을 최대한 많이 유지하는 것은 고전적인 활동 선택 문제를 다른 모습으로 표현한 것입니다. 같은 그리디 아이디어로 두 문제를 모두 해결할 수 있습니다.

여기서 가장 좋은 순서는 시작 시점이 아니라 끝나는 시점순입니다. 일찍 끝내야 다음에 유지할 수 있는 구간을 위해 시간 흐름을 가장 빨리 비울 수 있습니다.

아직 호환되는 구간 중 가장 일찍 끝나는 구간을 항상 유지하십시오. 그러면 나머지 구간을 위한 공간이 최대한 많이 남습니다.

마지막으로 유지한 구간의 끝 시점을 저장합니다. 다음 구간은 그 시작 시점이 해당 경계 이상일 때만 호환됩니다.

구간이 last_end보다 앞에서 시작하면 충돌하므로 해당 구간을 제외하고 제거 횟수를 1 늘립니다. 그렇지 않으면 유지합니다.

교환 논리로 증명할 수 있습니다. 유지한 구간을 호환되는 구간 중 가장 일찍 끝나는 구간으로 바꾸어도 유지할 수 있는 구간의 수는 절대 줄어들지 않습니다.

[1, 2]와 [2, 3]을 겹치는 것으로 셀지 결정하십시오. 끝점만 공유하는 것이 허용된다면 테스트에 start >= last_end를 사용하십시오.

끝나는 시점순으로 정렬하고 한 번 훑으면서 충돌을 셉니다. 전체 비용은 정렬에 필요한 O(n log n)과 한 번의 선형 순회로 이루어집니다.

이 패턴은 한 방에서 최대한 많은 회의를 배정하거나 한 기계에서 최대한 많은 작업을 처리할 때 사용됩니다. 충돌을 최소화해야 하는 상황에서 이 패턴을 알아보십시오.

겹치지 않는 구간을 그리디하게 유지합니다.

최소 제거 횟수는 n에서 유지할 수 있는 최대 개수를 뺀 값입니다. 끝나는 시점순으로 정렬하고, 가장 일찍 끝나면서 호환되는 구간을 그리디하게 유지한 뒤 나머지를 셉니다. 🚀