백준, 강의실 배정, 11000, 파이썬

[유형]

heap

 

[문제링크]

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

 

[요약]

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

 

[문제풀이]

시작 시간이 빠른 순으로 정렬을 한다.

최소힙을 사용해서, 강의 끝나는 시간이 새로운 강의 시작 시간보다 느리면, 새로운 강의실을 사용한다.(heappush)

import sys
import heapq
def input():
    return sys.stdin.readline().rstrip()
times= []
N = int(input())
for N in range(N):
    start,end = map(int,input().split())
    times.append([start,end])

times.sort()

room = []
heapq.heappush(room, times[0][1])

for i in range(1,N+1):
    if times[i][0]<room[0]:
        heapq.heappush(room, times[i][1])
    else:
        heapq.heappop(room)
        heapq.heappush(room, times[i][1])

print(len(room))