[우선순위 큐] 백준-11000 강의실 배정 골드4 (Python)

백준-11000 : 강의실 배정

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

11000번: 강의실 배정

 

풀의

• 입력 받은 강의 정보들을 시작 시간 기준으로 정렬한다.
• 우선순위 큐에 강의 정보의 첫번쨰 값의 끝나는 시간을 넣어준다.
• 강의 리스트를 순회하며 
  • 우선순위 큐의 첫번째 값보다 작다면 해당 강의실에서 강의 가능한 값이므로 끝나는 값으로갱신한다.
  • 우선순위 큐의 첫번째 값보다 크다면 강의실을 하나더 추가해야 함으로 끝나는 값을 우선순위 큐에 넣어준다.

 

코드 (Python)

import sys
import heapq

def input():
    return sys.stdin.readline().rstrip()

n = int(input())

lecture_list = [list(map(int, input().split(" "))) for _ in range(n)]

# 시작 순으로 정렬
lecture_list.sort(key=lambda x : x[0])

heap = [lecture_list[0][1]]

for start,end in lecture_list[1:]:
    if heap[0] <= start:
        heapq.heappop(heap)
    heapq.heappush(heap,end)

print(len(heap))