BOJ 1689 - 겹치는 선분

문제

수직선 위에 N개의 선분이 있을 때, 한 점에서 겹치는 선분의 최대 개수를 구하라. 선분의 끝점은 겹침에 포함하지 않는다.

입력

첫째 줄에 N, 이후 N줄에 각 선분의 시작점과 끝점이 주어진다.

출력

한 점에서 겹치는 선분의 최대 개수를 출력한다.

예제

입력	출력
`4` `0 3` `1 4` `2 5` `3 6`	`3`

풀이

시작점 기준으로 정렬한 뒤, 최소 힙으로 활성 선분의 끝점을 관리하여 스위핑한다.

선분을 시작점 오름차순으로 정렬한다
첫 선분의 끝점을 최소 힙에 넣는다
이후 선분을 순회하며, 힙에서 현재 시작점 이하인 끝점을 모두 제거한다 (끝점은 겹침 불포함)
현재 선분의 끝점을 힙에 추가하고, 힙 크기의 최댓값을 갱신한다

핵심 아이디어: 최소 힙으로 끝점을 관리하면, 새 선분 시작 시 이미 끝난 선분을 효율적으로 제거하여 현재 겹침 수를 O(N log N)에 추적할 수 있다.

코드

import sys, heapq
 
input = sys.stdin.readline
n = int(input())
array = [tuple(map(int, input().split())) for _ in range(n)]
array.sort(key=lambda x: x[0])
min_heap = []
heapq.heappush(min_heap, array[0][1])
result = 1
for x in array[1:]:
    while min_heap and min_heap[0] <= x[0]:
        heapq.heappop(min_heap)
    heapq.heappush(min_heap, x[1])
    result = max(result, len(min_heap))
 
print(result)

복잡도

시간: O(N * log N)
공간: O(N)

문제