[백준] 11000 강의실 배정

문제

• Si에 시작해 Ti에 끝나는 N개의 수업이 주어질 때, 최소의 몇 개의 강의실이 필요한가?
• 수업이 끝난 직후에 다른 수업을 시작할 수 있다.
• 1 <= N <= 200,000
  0 <= Si < Ti <= 10^9

 

풀이

• 빨리 시작하고, 일찍 끝나는 수업 순으로 정렬하고 하나씩 확인한다.
• 사용 중인 강의실 중에서 들어갈 수 있는 곳이 있나 확인하고, 없으면 새로운 강의실로 배정한다. 

 

import heapq
import sys
input = sys.stdin.readline

N = int(input())
time = [list(map(int, input().split())) for _ in range(N)]
# 빨리 시작하고, 일찍 끝나는 수업 순으로 정렬
time.sort(key=lambda x: (-x[0], -(x[1]-x[0])))

h = [time.pop()[1]]

while time :
    s, t = time.pop()
    if s >= h[0] :
        heapq.heappop(h)
    heapq.heappush(h, t)

print(len(h))

 

References

• 백준 그리디