백준 온라인 저지, 그리디 / 1689번: 겹치는선분 (파이썬 / 백준 골드문제)

문제

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

문제 정의

1차원 좌표계 위에 선분 N개가 있다. 선분이 최대로 겹쳐있는 부분의 겹친 선분의 개수를 구해보자. 선분의 끝 점에서 겹치는 것은 겹치는 것으로 세지 않는다.

입력

첫째 줄에는 선분의 개수(1 ≤ N ≤ 1,000,000)가 입력으로 들어온다. 그 다음 N개의 줄에 선분의 시작 좌표와 끝나는 좌표가 입력으로 들어온다. 선분의 좌표는 절댓값이 10억보다 작거나 같은 정수이다.

출력

첫째 줄에는 최대로 많이 겹치는 선분들의 개수를 출력한다.

예제 입력 1

11
1 2
3 6
7 8
10 11
13 16
0 5
5 6
2 5
6 10
9 14
12 15

예제 출력 1

3

접근 방법

- 선분을 입력받은 뒤 선분의 왼쪽 좌표를 기준으로 오름차순 정렬하고 첫번째 인덱스에 있는 오른쪽 좌표를 min heap에 저장한다.
- 이후 선분을 하나씩 탐색하며 탐색중인 선분의 왼쪽 좌표와 min heap에 저장된 오른쪽 좌표를 비교해 왼쪽좌표보다 낮은거는 모두 삭제한다.
- 삭제가 끝나면 현재 탐색중인 선분의 오른쪽 좌표를 min heap에 삽입한 뒤 결과 값에 결과값과 길이 중 더 높은 숫자를 저장한다.
- 모든 탐색이 끝난 뒤 결과값을 출력한다.

코드

# 접근 방법
# 선분을 입력받은 뒤 선분의 왼쪽 좌표를 기준으로 오름차순 정렬하고 첫번째 인덱스에 있는 오른쪽 좌표를 min heap에 저장한다.
# 이후 선분을 하나씩 탐색하며 탐색중인 선분의 왼쪽 좌표와 min heap에 저장된 오른쪽 좌표를 비교해 왼쪽좌표보다 낮은거는 모두 삭제한다.
# 삭제가 끝나면 현재 탐색중인 선분의 오른쪽 좌표를 min heap에 삽입한 뒤 결과 값에 결과값과 길이 중 더 높은 숫자를 저장한다.
# 모든 탐색이 끝난 뒤 결과값을 출력한다.
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)