[백준 / Python] 11000번 강의실 배정

문제

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

 

 

---

코드

import heapq
# 3
# 1 3
# 2 4
# 3 5
heap = []
# heapq.heappush(heap, 50)
# heapq.heappush(heap, 10)
# heapq.heappush(heap, 20)
n = int(input())
datalist = []
size = 0

for i in range(n):
    datalist.append(tuple(map(int, input().split())))
datalist.sort(key=lambda x : (x[0]))

# print(datalist)

# data (int, int)
for data in datalist:
    if len(heap) > 0:
        if heap[0] <= data[0]: # 끝 시간이 같거나 작을때-> 하여간에 회의실이 빌때 
            heapq.heappop(heap)
            heapq.heappush(heap, data[1])
        else:
            heapq.heappush(heap, data[1])
    else:
        heapq.heappush(heap, data[1])
print(len(heap))

 

---

풀이

 

(a, b)로 입력을 받았을때 a가 강의 시작 시각, b가 강의 끝나는 시각이다. 

 

(a, b)의 나열을 c라고 가정하였을때 

코드의 실행은 다음과 같다 

 

입력을 받아 c리스트를 a를 기준으로 정렬한다.

인덱스를 가르키는 int 변수(index , 초기 0)를 만든다.

 

index가 가르키는 c의 (a, b)를 우선순위큐의 맨위와 비교한다. 

- 우선순위큐 맨위의 강의 종료시간이 같거나 작다면 우선순위큐의 제일 상단 하나를 빼고 (a, b)를 넣는다. 

- 우선순위큐에 (a, b)를 넣는다. 

- index를 하나 올리고 반복한다. 

 

위 반복문을 진행하고 끝났을때의 우선순위큐의 길이를 출력하면 자연스럽게 최대로 쓴 강의실의 개수가 나옵니다.