Line Sweep 알고리즘

라인 스윕 알고리즘이란?

• 2차원 상 평면의 사건들을 x/y축으로 정렬 한 후, 한 방향으로 선을 쓸면서 사건들을 시간순으로 처리한다.

왜 쓸까?

• 구간, 직선, 사각형 등의 겹침여부 / 갯수 처리
• 1차원 혹은 2차원 공간에서 이벤트의 시작과 끝 처리

핵심 아이디어

1. 모든 사건을 이벤트 로 벼환한다.

• Ex. [1, 4] -> 1에서 시작해서 4에서 끝 -> (1, +1), (4, -1)

2. 이벤트를 정렬한다.

• Ex. 시간순으로 시작이 끝보다 먼저 오게

3. 선을 왼쪽에서 오른쪽으로 쭉 스캔하며 처리

---

예제

1. 미팅에 필요한 방 갯수 구하기

events = [
    (0, 30),
    (5, 10),
    (15, 20),
]

## 첫번째로 주어진 이벤트들을 사용하기 좋게 변환

converted = []

for start, end in events:
    converted.append((start, 1))
    converted.append((end, -1))

## 정렬 후 카운팅

ans = cnt = 0

converted.sort(key=lambda k: k[0])

for _, v in converted:
    cnt += v
    ans = max(ans, cnt)

print(ans)

• 여기서 (start, 1)은 미팅이 시작할때 방을 1개 더 필요로 하게 되는것이며, (end, -1)은 미팅이 끝나면 방을 사용하지 않게됨을 의미한다.