백준 11000 파이썬

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

11000번: 강의실 배정

 

 

 

import sys
import heapq

N = int(sys.stdin.readline())
class_list = []
for _ in range(N):
    S, T = map(int, sys.stdin.readline().rstrip().split())
    class_list.append((S, T))

class_list.sort()
# print(class_list)
q = []
for c in class_list:
    if q and q[0] <= c[0]:
        heapq.heappop(q)
    heapq.heappush(q, c[1])
print(len(q))

# 6
# 1 3
# 2 5
# 7 8
# 4 12
# 9 10
# 7 11
# 3
# 999999999 1000000000
# 999999998 999999999
# 1 999999998
#
# 답 : 1
# 출력 : 2

 

 

회의실 배정 문제와 비슷하다.

 

회의실 배정 문제에서는 이어서 할 수 있는 수업의 숫자만 구하고 나머지는 버려도 됐지만,

 

이문제에서는 모든 수업에 대해 이어서 할 수 있는 수업과 그렇지 못한 수업을 구해야한다.

 

1. 수업리스트를 시작시간 기준으로 정렬한다.

 

2. 수업리스트를 순회하면서 수업 종료시간을 우선순위 큐에 담는다.

 

3. 우선순위 큐에 값이 존재하고 현재 순회중인 수업 시작시간이 큐에서 가장 먼저 끝나는 종료시간과 같거나 이후라면 즉, 수업을 이어서 한 강의실에서 할 수 있다면 우선순위 큐에 있는 수업 종료시간을 제거한다.

 

4. 이런 식으로 마지막까지 순회하면 한 강의실에서 이어서 가능한 수업은 하나의 항목만 남는다. 3의 과정에서 이어서 할 수 있는 수업이면 우선순위 큐에서 이전수업을 제거하기 때문이다.

 

5. 최종적으로 우선순위큐에 담긴 갯수가 필요한 강의실 수 이다.