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