STUDY/algorithm with BOJ
[라인 스위핑]
officialhoyoon
2024. 7. 20. 20:51
| contents | dated |
| 라인 스위핑 개념 + 백준 2017번 |
2024.07.20 |
라인 스위핑(line Sweeping) 알고리즘은
선 하나를 여러 가지 상황에서 움직이면서 문제를 해결하는 것이다.
즉 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준을 적용해 주면 정답이
정답이 구해지는 형태이다.
정렬된 요소들을 한 번만 순회하면 연산 하면 정답이 나오는 구조 이다,
backjoon 2107번
import sys
input = sys.stdin.readline
n = int(input())
lines = []
for _ in range(n):
lines.append(tuple(map(int, input().split())))
lines.sort()
left = lines[0][0]
right = lines[0][1]
ans = 0
for i in range(1, n):
if right >= lines[i][1]:
continue
elif lines[i][0] <= right < lines[i][1]:
right = lines[i][1]
elif right < lines[i][0]:
ans += right - left
left = lines[i][0]
right = lines[i][1]
ans += right - left
print(ans)
