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

강의실 배정 성공

11000번: 강의실 배정

문제

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

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

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

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

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

 

내 코드

import heapq
import sys

n=int(sys.stdin.readline())
arr=[] #강의를 저장할 리스
heap=[] #힙

for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))

arr.sort(key=lambda x: x[0]) #빠른시작시간으로 정렬

cnt=int(1) # 필요한 강의실 수(1개부터 시작)
heapq.heappush(heap, arr.pop(0)[1]) #첫번째 강의의 끝나는 시간은 일단 push

for x in arr:
    if x[0]>=heap[0]: #탐색한놈의 시작시간이 힙에있는 시간(종료시간)보다 느리면 강의실 필요 X
        heapq.heappop(heap) #최상단 놈을 빼고
        heapq.heappush(heap, x[1]) #제일 빠른 종료시간을 update
    else: #탐색한놈의 시작시간이 힙에있는 시간보다 빠르면 강의실 필요
        heapq.heappush(heap, x[1]) #제일 빠른 종료시간을 update
        cnt+=1 #강의실 개수 추가
        
print(cnt)

 

풀이 및 접근

- 일단 시작시간이 빠른놈으로 정렬하고 시작

- 첫번째 강의는 일단 무조건 강의실이 하나 필요함. arr에서 첫번째 강의를 pop한다. 그러면서 첫번째 강의의 종료시간을 heap에 추가

- arr에 남아있는 모든 강의들을 돌면서, 해당 강의의 시작시간이 힙의 top보다 작으면 강의실을 하나 추가하고 해당 강의의 종료시간을 힙에 추가.

- 해당 강의의 시작시간이 힙의 top보다 크거나 같으면 강의실을 개설할 필요없고, top을 pop하고 해당 강의의 종료시간을 추가.

- cnt에 강의실 개수가 누적되어 있다

- 리스트에서 특정 원소를 기준으로 정렬하는 것이 포인트... arr.sort(key=lambda x:x[0])