ps:maximum_overlapping_intervals
Maximum overlapping intervals
- 구간들이 여러개 주어졌을때, 구간이 가장 많이 겹치는 점에서의 갯수를 구하는 문제.
- 그리디 알고리즘의 대표적인 예제문제인 최소 강의실 배정과 동일한 문제가 된다.
- 구간 쿼리 문제로 생각하면 구간들에 대해서 구간 업데이트를 해주고, 구간내의 최대 값을 찾으면 되기는 한다
- 이 작업에 그대로 대응되는 자료구조는 range add 업데이트와 max 쿼리를 지원하는 레이지 세그먼트 트리이다. 오버킬 느낌이 있긴 하지만, 그냥 이걸 무지성으로 가져다 써도 업데이트와 쿼리를 모두 O(logm)에 처리할 수 있다 (m=점들의 범위). n개의 업데이트와 1개의 쿼리를 처리하는 것이므로 시간복잡도는 O(nlogm).
- 하지만, 이 경우는 업데이트가 모두 끝난 뒤에 쿼리를 처리하는 개념이니까, 계차수열 트릭을 사용하면 복잡한 자료구조 없이 누적합 배열로 처리할수 있다. 시간면에서도 당연히 훨씬 효율적이다
- 구간의 시작점에는 +1, 구간의 끝점에는 -1을 더해준뒤, 누적합 배열을 계산해서 그중에서 최댓값을 찾는 방법이다
- 구간들의 범위 m이 작은 경우에는 이 편이 O(n+m)으로 빠르다.
- 구간들의 범위가 크면 좌표압축을 써서 이 방식을 계속 쓸수도 있지만 그럴바에는 아래처럼 스위핑으로 처리하는것이 더 낫다
- 보통은 스위핑으로 해결하는 것이 더 일반적이다
- 구간의 시작점과 끝점들을 모두 모아 정렬한 다음, 시작점에서는 카운트를 증가, 끝점에서는 카운트를 감소시킨다. 이 카운트가 의미하는 것이 겹치는 구간의 개수이므로, 카운트가 가장 클때의 값과 그때의 인덱스가 원하는 답이 된다.
- 시간복잡도는 정렬에 드는 O(nlogn)에 바운드된다.
- 우선순위 큐를 사용하는 풀이도 있는데, 그냥 다 정렬해놓고 처리하는 방법과 같은 원리이고 구현상 이득은 없다.
- 사실 두방법 다 생각하는 관점의 차이이지 실제로 별 차이는 없다. 스위핑 방식에서 정렬하는 것을 카운팅 소트로 처리했다고 생각하면 누적합 배열 방식이랑 거의 비슷해진다.
- 관련 문제
- Interval partitioning 에 있는 문제들
- 난개발 : 구간마다 가중치가 있는 경우
ps/maximum_overlapping_intervals.txt · 마지막으로 수정됨: 2023/08/31 05:38 저자 teferi
토론