백준 11000: 강의실 배정 해설 - python

✏️ 문제

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

11000번: 강의실 배정

백준 11000

 

✏️ 풀이

그리디 알고리즘 공부하겠다고 푼거긴한데 우선순위큐가 핵심인 문제인 것 같다.

 

• 회의의 [시작, 끝]을 리스트에 입력받는다.
• 회의시작시간을 기준으로 정렬시킨다.
• 첫 회의의 종료시간을 새로운 큐를 만들어 저장시킨다.
• 그 다음 반복문으로 두번째 회의의 시작시간부터 비교하면서 회의가 가능하면 회의가 진행되었다고 생각하고 새로운 큐를 업데이트해주고 회의가 불가능한 시간이면(회의겹치면) 새로운 큐에 push를 해주어 강의실이 하나 더 생긴 상황을 만들어준다. 이때 큐가 정렬상태를 유지하기 위해서 파이썬의 heapq 모듈을 이용하였다.

import heapq
from sys import stdin

n=int(stdin.readline())
heap=[]

for i in range(n):
  start, end=map(int, stdin.readline().split())
  heap.append([start, end])
heap.sort()

room = []
heapq.heappush(room, heap[0][1]) # 첫 강의 종료시간

for i in range(1, n):
  if heap[i][0]<room[0]: # 지금 강의 종료시간보다 다음 강의시작이 빠를때
    heapq.heappush(room, heap[i][1])
  else: # 지금 강의 끝나고 이어서 강의하면 됨
    heapq.heappop(room)
    heapq.heappush(room, heap[i][1])

print(len(room))