[python] 백준 2170 선 긋기

https://www.acmicpc.net/problem/2170

2170번: 선 긋기

 

문제 해결

• n과 x, y의 범위가 매우 크기 때문에 리스트를 만들어서 0,1로 색칠하기를 할 수는 없다.
• 그러면 주어진 범위를 가지고 한번에 길이 범위를 수정해야 한다.
• 결국 리스트 안에 범위를 다 넣고 lowerbound를 오름차순 한 다음 다음 범위와 연결 되는지 안되는지 확인하면 끝
• 단 python3로는 시간초과가 뜨고 pypy3로 성공했다. (n이 지나치게 크고 sort를 한번 해서 제법 큰거 같다.)

 

CODE

n = int(input())
Data = []
for _ in range(n):
    Data.append(tuple(map(int, input().split())))

Data.sort()

left = Data[0][0]
right = Data[0][1]
ans = 0
for i in range(1,n):
    if right >= Data[i][1]: continue
    elif right < Data[i][0]:
        ans += right - left
        left = Data[i][0]
        right = Data[i][1]
    elif Data[i][0] <= right <= Data[i][1]:
        right = Data[i][1]
ans += right- left
print(ans)