[백준/파이썬] 11000 강의실 배정

#문제링크

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

11000번: 강의실 배정

#나의풀이

import sys
from heapq import heappush, heappop

if __name__=="__main__":
    N = int(sys.stdin.readline())
    classes = []
    for _ in range(N):
        start, end = map(int, sys.stdin.readline().split())
        classes.append([start, end])

    classes.sort(key=lambda x: x[0]))
    heap = []
    heappush(heap, classes[0][1])
    for i in range(1, N):
        if heap[0] > classes[i][0]:
            heappush(heap, classes[i][1])
        else:
            heappop(heap)
            heappush(heap, classes[i][1])
    print(len(heap))

#해설

기존 쉬운 그리디에 살짝 꼬아놓은 문제? 보통은 수업 문제로 연달아 할 수 있는 최대 수업개수가 나오는데 이번에는 특이한 문제였던것 같다.

 

간단히 설명하면 수업시작과 끝을 주어지고 기존 수업이 끝나기전에 다른 수업이 있다면 다른 강의실에서 해야한다.

그렇다면 start를 기준으로 정렬하면 각 수업 시간이 빠른것부터 정렬이 된다.

 

이후 강의실을 담을 배열을 만들고 우선순위큐로 첫번째 강의를 넣어준다. 그 다음 반복문은 첫번째 강의가 들어갔으니 0번부터 검사를 하는데 우선순위 큐에 들어있는 강의 종료 시간이 다음 수업에 시작시간보다 더 크다면 강의가 끝나는 시간을 강의실에 넣어주고 그게 아니라면 그 강의가 끝나고 강의실에서 수업이 바로 가능하니 강의를 꺼내고 다시 넣어주었다.

 

이후 강의실의 개수를 출력했다.