(백준-11000) 강의실 배정 - 파이썬

영관·2023년 3월 13일

G5 강의실배정 그리디 그리디 알고리즘 백준11000 우선순위 큐 정렬 파이썬

백준문제

목록 보기

10/11

문제

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

문제 이해

조건:

각 강의의 시작 시간과 종료 시간이 주어진다.
두개의 강의가 한 강의의 종료 시간과 시작시간이 동일할 경우 같은 강의실 사용이 가능하다.

구할것:

배정 강의실의 갯수를 구해야 합니다.

문제 접근

이 문제를 풀기 위해 생각해봐야 할 것은 조건입니다.

이전 강의의 종료 시간과 다음 강의의 시작 시간이 겹친다면 한 강의실로 두 강의를 모두 진행할 수 있습니다.

이전 강의의 종료 시간 <= 다음 강의의 시작 시간
-> 이 경우 한 강의실에서 두 강의 모두 수강이 가능합니다.
이전 강의의 종료 시간 > 다음 강의의 시작 시간
-> 이 경우 강의실을 추가해야 합니다.

이 두가지 경우를 이용하기 위해서는 우선순위 큐가 필요합니다.

빨리 시작하여 빨리 끝나는 순으로 강의를 정렬하여 비교하기 위함 입니다!

코드

import sys
import heapq
input = sys.stdin.readline

# 우선순위 큐 이용
# 우선순위 큐에 start, end시간 다 추가
# 가장 빠른 start시간의 강의 강의실에 배정
# 만약 start가 같은 경우 end가 빠른 강의 먼저 배정
n = int(input().strip())
class_time = []
for _ in range(n):
    start, end = map(int, input().strip().split())
    heapq.heappush(class_time, (start, end))

# start가 같은 경우 end순으로 오름차순 정렬하기 위해서 사용
class_time.sort()
room = []
while len(class_time) > 0:
    s_t, e_t = heapq.heappop(class_time)
    if len(room) == 0:
        heapq.heappush(room, e_t)
    else:
        # 시작시간이 종료시간보다 크거나 같다면
        if room[0] <= s_t:
            heapq.heappop(room)
            heapq.heappush(room, e_t)
        # 시작시간이 종료시간보다 작다면 강의실 추가
        else:
            heapq.heappush(room, e_t)
# print(room) 
print(len(room))