11000 : 강의실 배정

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

11000번: 강의실 배정

 

문제의 핵심이라고 생각한 부분은

쓰고 있는 강의실 수업의 종료 시간과 새 수업 시작 시간의 비교이다.

 

다음 수업의 시작 시간이 이전 수업 종료 시간보다 빠르다면 새 강의실을 사용해야 하고

이전 수업 종료 시간과 같거나 이후라면 새 강의실을 사용할 필요가 없다.

 

입력받은 N개의 수업을 빨리 시작하는 순으로 정렬 한 뒤, 처음 시작하는 수업의 종료 시간을 큐(Queue)에 넣는다.

 

(1) 다음 수업 시작 시간이 큐의 시간보다 크거나 같다면

     같은 강의실을 사용하는 경우이고 큐에서 pop한다.

(2) 다음 수업 시작 시간이 큐의 시간보다 작다면

     다른 강의실을 사용하는 경우이고 해당 수업이 끝나는 시간을 큐에 push한다.

 

구하는 강의실의 개수는 큐에 들어있는 원소의 수와 같다.

(파이썬의 heapq 모듈을 사용했다 !)

 

import sys, heapq

n = int(sys.stdin.readline())

time_list = []

for i in range(n):
    st, et = map(int, sys.stdin.readline().split())
    time_list.append([st, et])

time_list.sort()

queue = []
heapq.heappush(queue, time_list[0][1])


for i in range(1,n):
    if time_list[i][0] < queue[0]:
        heapq.heappush(queue, time_list[i][1])
    else:
        heapq.heappop(queue)
        heapq.heappush(queue, time_list[i][1])

print(len(queue))