최대 겹침을 위한 선분 스위프

한순간에 몇 개의 구간이 같은 시점을 포함할까요? 가장 높은 개수가 최대 겹침이며, 시간 흐름에서 가장 바쁜 지점입니다. 📈

전체 구간을 그대로 생각하지 마십시오. 각 구간을 두 개의 이벤트로 나누십시오. 시작할 때는 +1, 끝날 때는 -1을 기록합니다.

모든 구간에 대해 시작 이벤트와 끝 이벤트를 하나의 공용 목록에 추가합니다. 각 이벤트에는 위치와 +1 또는 -1의 변화량이 들어 있습니다.

시간 흐름을 왼쪽에서 오른쪽으로 훑으며 변화를 올바른 순서로 처리할 수 있도록 모든 이벤트를 위치순으로 정렬합니다.

정렬된 이벤트를 순서대로 살펴보면서 누적 카운터를 유지합니다. 이벤트를 지날 때마다 변화량을 더하면, 카운터가 현재 활성화된 구간의 개수가 됩니다.

업데이트할 때마다 카운터를 지금까지의 최댓값과 비교합니다. 카운터가 도달한 가장 큰 값이 최대 겹침입니다.

같은 위치에서는 순서가 중요합니다. x에서 끝나는 구간이 x에서 시작하는 구간보다 먼저 자리를 비워야 한다면, 같은 지점에서는 끝 이벤트를 시작 이벤트보다 앞에 정렬하십시오.

동률을 처리하는 깔끔한 방법은 튜플 정렬이 대신 처리하도록 변화량을 정하는 것입니다. 위치가 같을 때 -1 변화량을 +1보다 앞에 두십시오.

2n개의 이벤트를 만들고 한 번 정렬한 다음 한 번 훑습니다. 한 번의 정렬이 지배하므로 전체 방법의 시간 복잡도는 O(n log n)입니다.

최대 겹침은 회의에 필요한 최소 방 수나 서버의 동시 접속자 수의 최댓값처럼 고전적인 문제의 답을 구하는 데 사용됩니다.

같은 스윕을 쉽게 확장할 수 있습니다. 전체 포함 길이를 추적하거나, 한 번의 선형 순회로 개수가 바뀌는 모든 위치를 찾을 수도 있습니다.

이벤트를 스윕하여 최대 겹침을 찾습니다.

구간을 +1 시작 이벤트와 -1 끝 이벤트로 바꾸고, 정렬한 뒤 카운터를 스윕하여 최댓값을 찾습니다. 끝나는 이벤트를 시작하는 이벤트보다 먼저 처리하여 동률을 해결하십시오. 🚀