백준 11000 강의실 배정

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

11000번: 강의실 배정

📌 해결순서

회의실 배정

[백준] 파이썬 1931 : 회의실 배정

신입사원

[백준] 파이썬 1946 : 신입사원

뭔가 이 두 문제를  합친 느낌이다

우선, 강의 시작 시간이 빠른 순서대로 정렬을 해준다.

강의실에서 강의가 끝나는 시간을 저장해두는 배열의 길이가 강의실의 수다.

heap 우선순위 큐를 사용해서 가장 빨리 끝나는 강의에 우선순위를 줬다.

강의가 빨리 끝나야지 다음 강의가 강의실을 추가하지 않고 사용할 수 있기 때문이다.

현재, 강의실을 사용하고 있는 강의중에 가장 빨리 끝나는 강의보다 현재 강의가 더 빨리 시작한다면 강의실을 추가해줘야 한다.

 

1. 강의실을 추가하는 경우

2. 강의실을 추가하지 않는 경우

📌 코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())

lectures = [list(map(int, input().split())) for _ in range(n)]
lectures.sort(key=lambda x: x[0])

end_times = []
while lectures:
    current_lecture = heapq.heappop(lectures)

    if end_times and current_lecture[0] >= end_times[0]:
        heapq.heappop(end_times)
    heapq.heappush(end_times, current_lecture[1])

print(len(end_times))