이 문제는 원 위의 특정 범위를 나타내는 구간들이 주어졌을 때, 구간 전체가 다른 한 구간에 포함되는 경우가 없는 구간들을 구하는 문제이다.
- 1번과 2번 부분 문제의 경우, 모든 쌍에 대해 구간들을 비교하면서 서로 포함하는지 아닌지 검사하는 것으로 해결할 수 있으며, 시간복잡도는 O(M^2)이다.
- 3번 부분 문제의 경우 구간들이 원 위가 아닌 직선 위에 주어지는 경우이다. 먼저 주어진 구간들을 시작점이 증가하는 순서대로, 같다면 끝점이 감소하는 순서대로 정렬한다. A 구간이 B 구간을 포함하려면 A 구간의 시작점과 끝점은 B 구간의 시작점과 끝점을 완전히 포함해야 한다. 결국 위와 같이 구간들을 정렬하면 뒤쪽에 있는 구간이 앞쪽에 있는 구간을 포함하게 되는 경우는 없다. 그러므로 정렬된 순서대로 구간을 확인하면서 이전까지 나온 구간의 끝점 중에 가장 먼 곳과 현재의 구간을 비교한다. 만약 작거나 같다면, 현재의 구간은 이전의 어느 구간에 포함된다는 뜻이고, 아닌 경우에는 끝점 중에 가장 먼 곳을 현재 구간의 끝점으로 갱신해주면 된다. 구간의 정렬에 O(M logM) , 구간 포함 관계 계산에 O(M) 이 소요되므로 O(M logM)의 시간복잡도로 해결할 수 있다.
- 4번 부분 문제는 구간이 원 위에 주어진 경우이다. 구간 [a,b]들이 a < b인 경우와 a > b인 경우를 따로 나누어서 저장하고, 각각을 그룹A, 그룹B이라고 한다. 이 때 그룹A의 구간은 (N-1)∼ 0 구간을 포함하지 않지만 그룹B는 (N-1)∼0 구간을 항상 포함하기 때문에 그룹A는 그룹B를 포함할 수 없다. 그렇기에 그룹B에 속하는 구간의 a의 최솟값과 b의 최댓값을 구하는 것으로 그룹A의 구간이 그룹B의 구간에 포함되는 경우를 쉽게 알 수 있다. 각각 의 그룹에 대해서는 3번 부분문제와 같은 방법으로 문제를 해결할 수 있다.
그리고 위의 해법을 조금 더 발전시키면, 그룹B에 있는 구간들의 가장 먼 끝점을 찾아 그룹 B에 포함되는 그룹A의 구간을 찾은 다음, 그룹B의 구간 [a,b]를 [a,b+N]으로 바꾸어 3번 부분문제와 같은 방법으로 그룹A와 그룹B 각각 서로에게 포함되는 구간을 O(MlogM)에 확인하여 답을 구할 수 있다.