백준 온라인 저지, 자료구조 / 12764번: 싸지방에간준하 (파이썬 / 백준 골드문제)

문제

현재 대한민국 해군에 소속되어있는 준하는 문제를 풀기 위해 매일같이 사이버 지식 정보방 통칭 싸지방에 다닌다. 그러나 최근 문제가 생겼다. 싸지방에 사람이 몰려 컴퓨터 수가 모자라게 된 것이다. 이런 사태를 도저히 용납할 수 없었던 준하는 곧 전역하는 선임을 설득해 민원을 넣도록 하는 데 성공했다.

마침내 부대에서는 민원을 받아들이기로 하였고, 컴퓨터를 증설하기로 했다. 또한, 컴퓨터 간의 사용률에 따라 다른 성능의 컴퓨터를 설치하고자 한다.

하지만 예산이 부족해 사람 수 만큼 컴퓨터를 살 수가 없었다. 고심에 고심을 거듭한 준하는 모든 사람이 항상 정해진 시간에 싸지방을 이용한다는 사실을 발견했다.

컴퓨터가 있는 자리에는 1번부터 순서대로 번호가 매겨져 있다. 모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이다.

준하가 발견한 사실과 이용 규칙을 가지고, 모든 사람이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하시오.

입력

첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000,000)\)

시작 시각이나 종료 시각이 다른 사람과 겹치는 경우는 없다.

출력

첫째 줄에 사람이 모든 사람이 기다리지 않아도 되는 컴퓨터의 최소 개수 \(X\)를 출력한다.

둘째 줄에는 1번 자리부터 \(X\)번 자리까지 순서대로 각 자리를 사용한 사람의 수를 띄어쓰기 간격으로 출력한다.

제한

예제 입력 1

5
20 50
10 100
30 120
60 110
80 90

예제 출력 1

4
1 2 1 1

힌트

접근 방법

- 컴퓨터 이용 시간을 컴퓨터 이용 시작 시간을 기준으로 오름차순 정렬한다.
- 이후 컴퓨터 이용 시간을 하나씩 탐색하며 다음과 같은 동작을 반복한다.
- 최소힙을 탐색하며 이용 종료 시간보다 작은 수가 있을 경우 이를 반복해서 삭제한다.
- 이후 최소 힙에 끝나는 시간을 삽입하고 힙의 최대 길이를 저장하고 현재 자리에 대한 정보를 최소 힙으로 관리하여 자리를 빼주거나 삽입한다.
- 모든 탐색이 종료되고 힙의 최대 길이를 출력한다.

코드

# https://www.acmicpc.net/problem/12764
# 접근 방법
# 컴퓨터 이용 시간을 컴퓨터 이용 시작 시간을 기준으로 오름차순 정렬한다.
# 이후 컴퓨터 이용 시간을 하나씩 탐색하며 다음과 같은 동작을 반복한다.
# 최소힙을 탐색하며 이용 종료 시간보다 작은 수가 있을 경우 이를 반복해서 삭제한다.
# 이후 최소 힙에 끝나는 시간을 삽입하고 힙의 최대 길이를 저장하고 현재 자리에 대한 정보를 최소 힙으로 관리하여 자리를 빼주거나 삽입한다.
# 모든 탐색이 종료되고 힙의 최대 길이를 출력한다.
import heapq, sys
input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
arr.sort(key = lambda x: x[0])
minH = []
seat = []
for i in range(1, n+1):
    heapq.heappush(seat, i)
count = [0 for _ in range(n+1)]
max_count = 0
for x in arr:
    while minH and x[0] >= minH[0][0]:
        end_time, s = heapq.heappop(minH)
        heapq.heappush(seat, s)
    s = heapq.heappop(seat)
    heapq.heappush(minH, [x[1], s])
    max_count = max(max_count, len(minH))
    count[s] += 1
print(max_count)
for i in range(1, max_count+1):
    print(count[i], end=' ')