작업 스케쥴링 (ex. 강의실 배정)

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

 

 

Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

 

 

1. 시작 시간 기준으로 정렬한다. 

2. 제일 빨리 시작하는 수업의 종료시간을 우선순위 큐에 삽입한다. 

    -. 다음 수업시간의 시작시간이 (가장 빨리 끝나는 이미 진행된 수업의 종료시간)보다 작으면 우선순위 큐에 넣는다

    -. 다음 수업시간의 시작시간이 ~~보다 더 크면 끝난 곳에 강의실을 배정하면 되니까 그냥 우선순위 큐를 팝 한다

5. heapq 에 남은 시간 수가 구해야 하는 강의실 개수다.

 

 

from heapq import heappush, heappop

n = int(input())

schedules = []
for _ in range(n):
    a, b = map(int, input().split())
    schedules.append((a, b))

schedules.sort()

q = []
heappush(q, schedules[0][1])

for i in range(1, n):
    if schedules[i][0] >= q[0]:
        heappop(q)

    heappush(q, schedules[i][1])

print(len(q))

 

 

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