Python/Greedy BOJ-11000 강의실 배정

Posted on | In

[Python/Greedy] BOJ-11000 강의실 배정

📌문제링크

최소 강의실을 사용해서 모든 수업을 가능하게 하는 문제다.
처음에 문제를 잘못읽어서 왜 틀린거지? 고민을 엄청했다. 문제를 잘! 읽자 ㅠ

heapq 는 자동으로 오름차순으로 정렬된다.
heapq.heappop : 0번째 값을 뱉음. 즉, 제일 작은 값을 뱉음

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys, heapq
input = sys.stdin.readline
if __name__=='__main__':
    N = int(input())
    timeboard = [list(map(int, input().split())) for _ in range(N)]
    timeboard = sorted(timeboard,key=lambda x:x[0])
    end = [] 
    heapq.heappush(end, timeboard[0][1])
    for i in range(1,N):
        if end[0] > timeboard[i][0]:
            heapq.heappush(end, timeboard[i][1])
        else: # 한 강의실에서 수업할 수 있는 경우
            heapq.heappop(end) 
            heapq.heappush(end,timeboard[i][1])
    print(len(end))