[BOJ] 2170번 - 선 긋기

 

[BOJ] 2170번 - 선 긋기

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

2170번: 선 긋기

 

주의할 점이 선을 긋는다고 하여 0부터 시작하는 것이 아닌 음수부터 시작이 된다 및 여러 번 그은 부분이나 한번 그은 부분이나 동일하게 계산되어야 한다.

 

알고리즘

---

그리디 알고리즘을 이용하여 풀었다.

시작점이 작은 좌표부터 시작하여 가장 긴 값을 찾아가는 형태로 찾아가면 최소 최대 길이를 구할 수 있다.

최소 값을 갱신하면서 찾아야 하기 때문에 Heap을 사용하여 풀었다.

 

1. Data 입력

2. 시작점이 최소인 값부터 시작

3. 다음 시작 지점이 끝나는 지점보다 더 크다면 현재값은 하나의 줄임으로 추가

4. 부분이 겹쳐있다면, start 와 end 지점을 갱신 시켜준다.

5. Queue가 없어질 떄 까지 3~4 계속

6. 이후 혹시 남아있을 값을 추가적으로 더해준다.

 

 

코드

---

#BOJ 2170번

import heapq
import sys
input = sys.stdin.readline

answer = 0
start , end = -1000000001 , -1000000001

n = int(input())
q = []

for _ in range(n) :
    x1,x2 = map(int,input().split())
    heapq.heappush(q,(x1,x2))

while q :
    x1 , x2 = heapq.heappop(q)
    if x1 > end :
        answer += end-start
        start , end = x1 , x2
        continue
    if start > x1 :
        start = x1
    if end < x2 :
        end = x2

answer += end-start
print(answer )