백준 2170 선 긋기 / python

문제 : 2170

풀이 point

겹친 부분을 알차라기 위해 우선 정렬이 필요하다. 시작 위치로 정렬된 순서에서 다음 선의 시작 위치가 이전 선의 마지막 위치에 포함되는지 아닌지를 따져야 한다.

풀이 방법

1. 포함되면
   포함된다면 그 선의 마지막 길이는 max(원래 마지막 길이, 현재 선 길이)이다.

2. 포함되지 않는다면
   포함되지 않는다면 지금까지 포함으로 계산된 선의 최종 길이를 구해준다.(정렬 되어있기 때문에 뒤에서 포함되는 선이 나올 수는 없다.) 그 다음 새로이 시작 위치와 끝 위치를 계산해서 저장한다.

풀이 코드

N = int(input())

lines = []
for _ in range(N):
  lines.append(list(map(int, input().split())))

lines.sort()

sums = 0
l, r = lines[0][0], lines[0][1]
for i in range(1, N):
  if lines[i][0] > r: #안겹침
    sums += r-l
    l, r = lines[i][0], lines[i][1]
  else:
    r = max(lines[i][1], r)

sums += r-l
print(sums)