[백준] 1374번 강의실 (파이썬)

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

난이도 : GOLD V

문제해결

• 우선순위큐를 활용한 문제
• 강의 시작시간으로 배열을 정렬 하고 힙에는 강의끝나는 시간을 추가한다.
• 배열을 순회하며 힙에 있는 강의 중 가장 일찍 끝나는 강의(최소힙)가 현재 순회중인 강의시작 시간보다 늦게 끝나면 힙에 순회중인 강의 추가, else: 최소힙을 pop 한다.

소스코드

import heapq

input = sys.stdin.readline

n = int(input())

arr = []

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

arr.sort(key=lambda x:x[1]) # 강의 시작순서로 오름차순 정렬

h = [arr[0][2]] #첫 강의 힙큐에 넣기
cnt = 1 # 강의실 수 default = 1
for i in arr[1:]: # 두번째 강의부터 순환
    while h: #남은 강의실이 없을때 까지
        if h[0] > i[1]: #진행중인 강의중 가장 빨리끝나는 강의가 순회중인 강의시작시간보다 늦으면
            break
        
				else:# 진행중인 강의가 더 빨리 끝날 경우
            heapq.heappop(h) #진행중인 강의 빼기
		
		heapq.heappush(h, i[2]) #순회중인 강의를 힙큐에 넣기
    cnt = max(cnt, len(h))

print(cnt)