백준 11000 강의실 배정

문제

https://www.acmicpc.net/problem/11000

코드

import sys
import heapq
input = sys.stdin.readline
n = int(input())

times = []
pq = []
for _ in range(n):
    s, t = map(int, input().split())
    times.append((s, t))
times.sort()
heapq.heappush(pq, times[0][1])

for i in range(1, n):
    # 가장 먼저 끝나는 강의보다 현재 강의가 늦게 시작하면 안겹치니까 빼주기
    if times[i][0] >= pq[0]:
        heapq.heappop(pq)

    # 다음 강의 끝나는 시간을 항상 heapq에 넣기 때문에 최댓값이 보존
    heapq.heappush(pq, times[i][1])

print(len(pq))

풀이

그리디 문제로 우선순위 큐를 사용해서 풀이 할 수 있습니다
먼저 강의를 시작시간 순으로 정렬 하고 순회를 돌면서 강의가 끝나는 시간을 우선순위 큐에 삽입하고, 만약 가장 먼저 끝나는 강의보다 현재 강의가 늦게 시작하면 강의가 안겹치는 것이기 때문에 큐에서 제거해줍니다