백준[11000] 강의실 배정 (파이썬 풀이)

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

11000번: 강의실 배정

 

내가 한 풀이

모든 강의를 최소한의 강의실을 사용해서 진행해야 한다.

=> 한 강의의 종료시간이 그 다음 강의 시간 보다 작아야 같은 강의실을 사용할 수 있다.

강의를 시작시간이 빠른 순으로 정렬한다. 

최소힙에 가장 빠른 강의의 종료시간을 넣어준다.

그 다음 강의의 시작시간을 탐색하며 최소힙 첫번째 원소(가장 빠른 강의 종료시간)보다 작을 경우에는 최소힙에 넣어주고,

클 경우에는 힙에서 첫번째 값을 해당 강의의 종료시간으로 갱신해준다.

모든 탐색이 종료된 후 힙의 길이가 사용된 강의실의 개수이다.

 

import heapq
import sys
input = sys.stdin.readline
n=int(input())
classes=[]
for _ in range(n):
    classes.append(list(map(int,input().split(" "))))
    
room=[]

classes.sort()
heapq.heappush(room,classes[0][1])

for i in range(1,len(classes)):
    if classes[i][0]<room[0]:
        heapq.heappush(room,classes[i][1])
    else:
        heapq.heappop(room)
        heapq.heappush(room,classes[i][1])
print(len(room))

이 문제의 경우 입력값 n의 크기가 최대 200,000이라 그냥 input()으로 받을 경우 시간 초과가 발생한다.

sys.stdin.readline()을 이용해 많은 양의 입력값을 받아야 통과했다.

또한 이중 for문을 쓸 경우 시간 초과가 발생하기 때문에 O(nlogn)으로 문제를 풀어야했다.