Problem
$n$개의 구간 $[L_i, R_i]$가 주어진다. ( $n \leq 200\ 000$ )
겹치지 않는 구간들을 최대한 많이 골라, 번호의 집합이 사전순으로 최소인 것을 찾아라.
Algorithm
각 구간에 대해 $2^i$ 번째 후의 구간 번호를 담는 Sparse Table을 만든다. $1$번 구간부터 차례대로 보면서 삽입했을 때 나뉜 두 구간에서 각각 최적해가 존재하는 지를 Sparse Table을 이용해서 확인하고, 존재한다면 답에 추가하는 과정을 반복하면 된다.
시간 복잡도는 $O(nlogn)$.
Idea
사전순으로 최소인 최적해를 찾기 위해, $1$번부터 순서대로 보면서 해당 구간을 포함하는 최적해가 존재하는 지 여부를 확인할 수 있으면 된다.
단순하게 매번 확인하는 것은 적어도 $O(n^2)$ 이 소요될 것으로 보이므로, 최적해에 대해 조금 더 관찰을 해 볼 필요가 있다.
가능한 여러가지 최적해들을 생각해보자. 구간 개수가 최대라는 조건 때문에, 서로 다른 최적해에서 선택된 구간들의 분포는 대충 비슷비슷할 것이다. 만약 그렇지 않다면, 적당한 다른 구간들을 선택해서 사이에 구간을 하나 더 끼워넣을 수 있는 형태로 변형이 가능할 것이라는 느낌이 든다.
또 우리는 그리디 알고리즘으로 다음의 특수한 두 가지 최적해를 찾을 수 있다는 것을 알고 있다.
- $k$ 번째로 선택된 구간의 $R$ 값이 각 $k$에 대해 최소인 해
- $k$ 번째로 선택된 구간의 $L$ 값이 각 $k$에 대해 최대인 해
대충 생각해서, “모든 구간이 가능한 한 왼쪽에 있는 해”와 “모든 구간이 가능한 한 오른쪽에 있는 해” 라고 생각해도 좋다. 각각 “왼쪽 해”와 “오른쪽 해”로 부르기로 하자.
그러면 이제 $ k $번째로 선택 가능한 구간의 후보가 어떤 범위로 주어질 것 같다는 생각이 든다. 약간의 시행착오를 거쳐, 다음 사실을 얻을 수 있다.
“왼쪽 해”에서 $k$ 번째 구간의 $R$값을 $R_k$, “오른쪽 해”에서 $k$번째 구간의 $L$값을 $L_k$라고 하면,
- $L_1 \leq R_1 < L_2 \leq R_2 <\ …\ < L_K \leq R_k$
- 어떤 구간 $[l, r]$이 $k$번째로 선택 가능한 후보일 필요충분조건은 $[l, r]$이 위의 값들 중 오직 $L_k$와 $R_k$ 만을 포함하는 것이다.
증명은 Case Work로 가능하다. 대부분 그 반대가 성립한다고 가정했을 때 “왼쪽 해” 또는 “오른쪽 해”의 성질에 모순이거나, 최적이라는 것에서 모순이 발생하는 식으로 증명된다.
이 성질을 이용하면 각 구간이 몇 번째로 선택될 수 있는 지에 대한 정보는 lower_bound, std::set, 세그먼트 트리 등을 이용해서 $O(log n)$ 에 찾을 수 있다.
이제 각 구간이 들어갈 수 있는 위치가 고정되었으므로, 문제 상황이 훨씬 간단해졌다. 구간의 위치가 고정되었기 때문에, 각 구간을 선택했을 때마다 인접한 다른 구간 사이에 추가적으로 몇 개의 구간을 더 선택해야 하는 지를 알 수 있다.
인접한 구간의 정보를 찾는 것은 std::set을 통해 $O(log n)$에 가능하다. 그러면 이제, 주어진 시간 범위 $[T_l, T_r]$ 에서 $k$개의 겹치지 않는 구간을 선택할 수 있는 지를 빠르게 확인할 수 있으면 문제가 해결되는데, 이는 Sparse Table을 이용하여 $O(log k)$ 시간에 가능하다.
Code
1 |
|