문제
풀이
스위핑, 훑는 문제이다. 시작점을 오름차순으로 sort하고 난 뒤, 선이 이어지는지 안이어지는지 여부를 따진다.
이어진다는 것은 기존의 끝점보다 시작점이 더 작은 경우가 이어진다. 이 때, 끝점은 기존의 끝점과 새로운 끝점 중에 큰 값이 되게 된다.
이어지지 않는 경우는, 기존의 끝점보다 시작점이 더 큰 경우로, 이 경우는 새롭게 시작점과 끝점을 설정하여 정답을 도출한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
iimport sys
li = []
ans = 0
n = int(input())
for i in range(n):
start, end = map(int, sys.stdin.readline().split()) # 입력때문에 시간초과 났음
li.append((start, end))
li.sort()
prevStart, prevEnd = li[0][0], li[0][1]
for i in range(1, n):
start, end = li[i][0], li[i][1]
if start <= prevEnd:
prevEnd = max(prevEnd, end)
else:
ans+=prevEnd-prevStart
prevStart, prevEnd = start, end
ans+=prevEnd-prevStart
print(ans)
