2170(선 긋기) - 해결

선 긋기

 

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

 

입력

첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

 

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

---

선을 긋기 때문에 포함하는지 여부를 판단해보려고 하였다.

그러기위해서 선을 하나 긋고 이어지는지 아니면 떨어지는지를 판단하려고하였다.

또한 이를 위해 시작점을 기준으로 정렬을 하여 이어지는지 여부를 판단하려고 하였다.

다음 시작점이 지금까지의 선에 포함되는지 보고 그렇게 되면 해당 선은 전의 선에 포함되거나 길어지게 만드는 것이다.

만약 해당 선이 전의 선에 포함 되지 않는다면 새로운 선이 만들어지는 것이기 때문에 지금까지 선의 길이를 저장하고 새로 시작을 한다.

이 과정을 다 한 후, 마지막으로 남은 선의 길이를 저장한다.

import sys
input = sys.stdin.readline

N = int(input())

total = 0

lines = [tuple(map(int,input().split())) for _ in range(N)]
# 시작점을 기준으로 정렬
lines.sort()

# 처음 선을 가지고 시작
st, ed = lines[0]

# 다음 선부터 판단
for i in range(1,N):
    # 현재 선의 시작, 끝
    a, b = lines[i]

    # 현재 시작이 지금까지의 선에 포함이 되면 
    # 현재 선은 지금까지의 선에 포함되거나 연장시킨다.
    if st <= a <= ed:
        # b가 더 크면 연장
        # ed가 크면 포함
        ed = max(b,ed)
    
    # 포함되거나 연장시키지 않으면 끊어진거기 때문에
    # 지금까지의 선 길이를 저장하고 새로 시작
    else:
        total += ed - st
        st, ed = a, b

# 마지막 선의 길이를 저장
total += ed - st

print(total)