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

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

 

기록

(greedy 7일차) 저번에 풀었던 문제(19598)과 비슷해서 금방 풀었다. 저번에는 heapq 사용해서 풀었는데 그 때 알게 된 간단한 방법이 있어서 이번에는 그렇게 풀어봤다. 최대로 중복되는 강의실 개수를 세는 방법이다.

힙 사용한 문제 풀이 >> 2021.07.16 - [알고리즘] - [백준 19598번] 최소 회의실 개수 (python)

 

코드

from sys import stdin

N = int(stdin.readline())
confs = []
for i in range(N):
    s, e = map(int, stdin.readline().split())
    confs.append((s, 1))
    confs.append((e, -1))
confs.sort(key=lambda x : (x[0], x[1]))

maxroom = 0
room = 0
for time, n in confs:
    room+=n
    if room>maxroom: maxroom=room

print(maxroom)

회의를 저장하는 배열에 시작시간이라면 (시작시간, 1), 도착시간이라면 (도착시간, -1)로 구분하여 모든 회의를 저장한다. 해당 배열을 돌면서 회의실개수 0에서 시작하여, 시작시간일 경우 +1(회의실을 빌린다), 도착시간일 경우 -1(회의실을 반납한다)을 하며 최대로 중복되는 회의실 개수를 출력한다.