[백준 11000] 강의실 배정 (python)

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

11000번: 강의실 배정

강의실 배정 문제

강의실을 배정하여 최소 강의실 수를 찾는 문제

 

# 사용 알고리즘

그리디

우선순위 큐

정렬

📌문제 접근 포인트

1. 강의실을 배정하기 위한 방법을 생각해보자. 그리디 방식을 생각하면, 먼저 시작시간 순서대로 강의실을 배정하고, 진행 중인 강의의 끝나는 시간과 새로운 강의의 시작시간을 비교해야한다.
2. 이를 위해 강의의 시작시간을 기준으로 정렬 후, 현재 사용 중인 강의실 중에서도 가장 먼저 진행한 강의(우선순위가 높은 강으)의 종료 시간과 비교를 하면서 진행해야 하므로 우선순위 큐를 사용해주자.
3. 우선순위 큐의 기능을 활용하여 시작시간  끝시간 < 시작시간 일 경우, 새로운 강의실을, 끝시간 > 시작시간 일 경우, 기존 강의를 제거하고 새로운 강의를 넣도록 구현하면 된다.

⚙ 내가 푼 정답 코드

import sys, heapq
N = int(sys.stdin.readline())
lecture = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(N)])
room = []
heapq.heappush(room,lecture[0][1]) # 첫 강의 끝나는 시간

for i in range(1,N):
    if lecture[i][0] < room[0]: # 강의의 시작 시간이 현재 강의 끝나는 시간 보다 짧으면
        heapq.heappush(room, lecture[i][1]) # 새로운 강의실을 넣자
    else: #아니면
        heapq.heappop(room) # 기존 강의를 빼내고
        heapq.heappush(room, lecture[i][1]) #해당 강의를 넣자
        
print(len(room))