문제링크 : 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)