99클럽 코테 스터디 19일차 TIL: 강의실 배정 그리디

오늘의 문제: 1374. 강의실

오늘도 딱봐도 그리디 문제다. 그리고 그리디 문제 중 가장 유명한 문제격인 강의실 배정과 비슷한 문제로 보인다. 오늘도 그리디적 사고를 해보려고 한다.

아이디어: 한 수업이 끝나고 가장 빨리 시작하는 수업을 바로 배정한다.

어차피 문제에서 구해야 하는 것은 동시에 최소 몇개의 강의실이 필요한가 이다. 즉 퍼즐을 맞추듯이 하면 되는거 아닌가? 그래서 그냥 한 가지 케이스만 존재하는게 아닌가? 하는 생각이 들었다. 근데 알고리즘 분류에 우선순위 큐가 존재한다… 우선순위 큐도 무엇인지 알아놔야 하는 것일까? 일단 풀어보기로 했다. 강의 번호는 필요없어 보이니 대충 버리고 시작했다.

• 처음 시작한 강의의 끝나는 시간을 저장함 → 해당 시간이 되기 전에는 빼지 않음.

import heapq

n=int(input())
l=[]
for i in range(n):
    k,a,b=map(int,input().split())
    l.append((a,b))
l.sort(key=lambda x: x[0])

end=[]
heapq.heapify(end)
maxlen=0

for i in l:
    a,b=i
    while end:
        temp=heapq.heappop(end)
        if temp>a: 
            heapq.heappush(end,temp)
            break
    end.append(b)
    maxlen=max(maxlen,len(end))
print(maxlen)

오늘의 회고

오늘은 문제 풀고 너무 뿌듯해서 바로 회고를 작성한다. 골드 문제를 알고리즘 힌트 하나만 보고 풀었다는게 만족스럽다. 확실히 그리디다보니 코드 자체가 길지 않은데, heapq를 오랜만에 썼음에도 활용법을 잊지 않고 잘 이용했다는 게 신기할 정도이다. 그리디도 이제 어느정도 적응을 하고 있구나라는 생각이 든다.