겹치는 직선 구간쌍의 개수 빠르게 세기

D - Intersecting Intervals (atcoder.jp)

D - Intersecting Intervals

 

 

50만개의 구간 [l,r]이 주어질때, 이들 중 서로 겹치는 구간 쌍의 개수가 몇개인지 구하는 문제

 

모든 구간 쌍에 대해 서로 겹치는지 조사할려면 $O(N^{2})$인데, 당연히 N이 최대 50만이므로 시간제한에 맞지 않는다

 

전체 구간 쌍의 개수는 n개중 2개를 선택하는 경우의 수이므로, nC2 = n(n-1)/2

 

만약 서로 겹치치 않는 구간 쌍의 개수를 구할 수 있다면, nC2에서 이 개수를 빼면 서로 겹치는 구간 쌍의 개수를 구할 수 있다

 

어떤 구간 i가 $l_{i}, r_{i}$이면, 이 구간 i와 공통 부분이 없는 구간은 $l_{j}, r_{j}$에 대하여, $r_{j} < l_{i}$를 만족해야한다.

 

그러므로 모든 i = 1,2,3,..,n에 대하여 $r_{j} < l_{i}$를 만족하는 j의 개수를 구해 더하면 된다.

 

 

[l,r]에 대하여 l을 모아둔 L과 r을 모아둔 R을 구하고 이들을 오름차순으로 정렬한다.

 

L1 < L2 < ... < LN

 

R1 < R2 < ... < RN

 

먼저 i = 0일때  j = 0부터 시작해서 $r_{j} < l_{i}$를 만족하면 j를 1씩 증가시킨다.

 

처음으로 $r_{j} > l_{i}$라면, 0~j-1까지가 $r_{j} < l_{i}$를 만족하므로 총 j개를 빼면 된다.

 

다음 i = 1로 가는데, 다시 j = 0부터 시작해서 $r_{j} < l_{i}$를 만족하면 j를 1씩 증가시키는 것을 반복해야할까?

 

이러면 여전히 $O(N^{2})$이다.

 

하지만 L,R이 오름차순으로 정렬되어 있기 때문에, $r_{j-1} < l_{i} < l_{i+1}$를 알 수 있다.

 

그러므로 이전에 i = 0일때 구해둔 j = 0,1,2,..,j-1까지는 여전히 $l_{i+1}$보다 작다.

 

이 구간들은 여전히 $l_{i+1},r_{i+1}$과 겹치지 않기 때문에 카운팅을 가지고 가줘야한다.

 

그래서 j = 0으로 바꾸지 않고 이 j부터 시작해서 $r_{j} > l_{i+1}$이 될 때 까지 j를 1씩 증가시키자.

 

$r_{j} > l_{i+1}$이면 다시 answer에 j를 빼준다.

 

이를 반복하면 O(N)이므로 전체는 정렬에 의한 시간복잡도 $O(NlogN)$에 해결할 수 있다

 

from sys import stdin

n = int(stdin.readline())

L = []
R = []

for _ in range(n):
    
    l,r = map(int,stdin.readline().split())

    L.append(l)
    R.append(r)

L.sort()
R.sort()

answer = n*(n-1)//2

j = 0

for i in range(n):

    while R[j] < L[i]:
        
        j += 1
    
    answer -= j

print(answer)