2170번: 선 긋기

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

아이디어

• start와 end는 각각 이어지는 긴 선분의 처음과 끝 부분이다.
• 튜플 (x, y)에서 x가 end보다 큰 경우, 새로운 선분임으로 취급한다.
  • 이 때, 새 선분 이전까지의 선분 길이를 정답에 더한다.
  • 이후 start와 end를 갱신한다.
• 일부만 포함된 경우, end값만 y로 갱신한다.
• 완전히 포함된 경우 선분 길이에 영향이 없으므로 아무 행동을 취하지 않는다.

# https://www.acmicpc.net/problem/2170
# sweeping
import sys

N = int(input())

lines = [0] * N
for idx in range(N) :
    x, y = map(int, sys.stdin.readline().split())
    lines[idx] = (x, y)

lines = sorted(lines, key=lambda x : (x[0], x[1]))

ans = 0
CRIT = -1000000001
start, end = CRIT, CRIT
for line in lines :
    x, y = line
    if start == CRIT and end == CRIT :
        start, end = x, y
        continue
    # 새로운 선분
    if end < x  :
        ans += abs(end - start)
        start, end = x, y
        
    # 일부만 포함된 선분
    elif start <= x <= end and y > end :
        end = y
    # 완전히 포함된 선분
    elif start <= x and y <= end :
        continue

ans += abs(end - start)
print(ans)