[Python] 백준 / gold / 11000번 (강의실 배정)

문제 링크 : https://www.acmicpc.net/problem/11000

그리디 알고리즘 문제이다.
"최소의 강의실을 사용해서 모든 수업을 가능하게 해야한다."

먼저 강의 시작 시간으로 정렬한 뒤, 강의 종료 시간으로 정렬한다.
시작 시간이 빠르고, 강의 시간이 짧은 강의 부터 처리하고 본다.

그리고, 따로 힙 자료구조를 생성하여 강의가 종료한 시간을 저장한다.
그리도 다음 강의 (lec) 를 탐색할 때, 힙에서 강의 종료가 가장 빨랐던 강의를 꺼내어 lec의 시작시간과 비교한다.

정답 코드

import sys
import heapq
N = int(input())
lecture = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

lecture.sort(key=lambda x: (x[0],x[1]))

end = []
heapq.heappush(end, lecture[0][1])
answer = 1

for lec in lecture[1:]:
    if lec[0] < end[0]:
        heapq.heappush(end, lec[1])
        answer += 1
    else:
        heapq.heappop(end)
        heapq.heappush(end, lec[1])
        answer += 0

print(answer)