Merging Intervals

먼저 어떤 구간이 다른 구간에 완전히 포함되어 있다고 하자. 포함하는 구간과 임의의 다른 구간을 고른 합집합은, 포함되는 구간과 같은 다른 구간을 고른 합집합보다 작지 않다. 따라서 다른 구간에 포함되는 구간은 최적의 답을 찾을 때 제거해도 된다.

구간을 $l$의 오름차순, $l$이 같다면 $r$의 내림차순으로 정렬한다. 왼쪽부터 보면서 지금까지 본 $r$의 최댓값보다 $r$이 크지 않은 구간을 제거한다. 남은 구간을

$$[l_1,r_1],[l_2,r_2],\cdots,[l_M,r_M]$$

이라 하면

$$l_1<l_2<\cdots<l_M,\qquad r_1<r_2<\cdots<r_M$$

이 성립한다.

원래 구간 중 가장 긴 구간의 길이를 정답의 초기값으로 둔다. 다른 모든 구간이 하나의 구간 안에 포함되는 경우에도 이 값이 정답이 된다.

이제 남은 구간에서 오른쪽 구간 $j$를 고정하자. $r_i<l_j$를 만족하는 가장 뒤쪽 경계와 $r_i\geq l_j$를 만족하는 가장 앞쪽 경계를 투 포인터로 관리한다.

$r_i<l_j$인 구간 $i$는 $j$번 구간과 서로 겹치지 않는다. 따라서 합집합 길이는

$$(r_i-l_i)+(r_j-l_j)$$

이다. 앞쪽 구간들의 길이 최댓값을 전처리하면 이 경우의 최댓값을 바로 구할 수 있다.

반대로 $r_i\geq l_j$인 구간들은 $j$번 구간과 겹치거나 한 점에서 만난다. 남은 구간들의 오른쪽 끝점은 엄격히 증가하므로 $r_i<r_j$이고, 합집합은

$$[l_i,r_j]$$

가 된다. 따라서 가능한 $i$ 중 $l_i$가 가장 작은, 즉 가장 앞쪽 구간을 고르는 것이 최적이다.

정렬에 $O(N\log N)$, 이후 전처리와 투 포인터에 $O(N)$이 걸리므로 전체 시간 복잡도는 $O(N\log N)$이다.

모든 구간은 $[0,10^9]$ 안에 있으므로 두 구간의 합집합도 이 범위를 벗어나지 않는다. 따라서 정답은 항상 $10^9$ 이하이며 부호 있는 $64$비트 정수 범위에 들어간다.

Solution written by GPT5.6