2170번 선 긋기

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

아이디어

한 쪽 방향에서 다른 쪽 방향으로 쓸어가는 알고리즘인 Sweeping 알고리즘을 이용했다.

시작 지점을 기준으로 정렬을 해야한다.
(문제에서 선분 순서대로 나온다는 말이 없기 때문!
start가 가장 왼쪽에 있는 선분부터 쓸어갈 예정)

이 문제의 경우는 세 가지이다.
1) 선분이 완전 겹치는 경우
2) 선분이 약간 겹치는 경우
3) 선분이 아예 다른 선분인 경우(안겹침)

하나씩 설명해보자면!
1) 선분이 완전 겹치는 경우
완전히 겹치기 때문에 start, end 지점을 바꿔줄 필요가 없다.
2) 선분이 약간 겹치는 경우
start는 냅두고 end만 더 큰 값으로 바꿔준다.
(그럼 좀 더 긴 선분이 됨)
3) 선분이 아예 다른 선분이 경우
정답에 선분의 길이를 더해준 후, 이제 새로운 선분이므로 start, end를 새로 갱신해준다.

---

코드

n = int(input())

lines = []
for _ in range(n):
    a, b = map(int, input().split())
    lines.append([a, b])
lines.sort(key=lambda x : x[0]) # 시작점으로 오름차순 정렬

start, end = lines[0][0], lines[0][1]
answer = 0 # 선들의 합
for i in range(1, n):
    if lines[i][0] <= end and lines[i][1] <= end: # 완전 겹치는 경우
        continue
    elif lines[i][0] <= end and lines[i][1] > end: # 약간 겹치는 경우
        end = lines[i][1]
    else: # 아예 안겹치는 경우
        answer += end - start
        start = lines[i][0]
        end = lines[i][1]
answer += end-start
print(answer)