[백준][2170] 선 긋기

• 문제
  • 2170번: 선 긋기
• 해결

import sys

N = int(sys.stdin.readline())
nlist = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]
nlist.sort()

cumulative_length = 0
cumulative_right_point = -sys.maxsize

for current_left, current_right in nlist:
    if current_left >= cumulative_right_point:
        cumulative_length += (current_right - current_left)
    else:
        if current_right > cumulative_right_point:
            cumulative_length += (current_right - cumulative_right_point)
    cumulative_right_point = max(current_right, cumulative_right_point)
print(cumulative_length)

• 포인트
  • input을 정렬하고(O(NlogN)) 좌측부터 우측으로 O(N)만 함
  • 이를 sweep line 기법이라 함