[알고리즘] BOJ 1374 강의실

[BOJ] 1374 강의실 바로가기

📍 문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

---

📍 입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

---

📍 출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

---

📍 풀이

✍ 문제 풀이

• 파이썬의 힙 모듈(heapq)을 이용하여 문제를 해결
  • heappush(리스트, 원소) : 리스트에 힙 형식으로 원소를 입력
  • heappop(리스트) : 리스트에 존재하는 가장 작은 값 출력
• 강의의 시작 시간을 기준으로 강의를 오름차순으로 정렬
• 힙에 가장 빨리 시작하는 강의의 종료 시간을 push() 한다.
• 모든 강의의 시작 시간(a)과 힙에 저장된 가장 빨리 끝나는 종료 시간(b)을 비교한다.
  • 만약 a >= b 라면 힙에 저장된 가장 빨리 끝나는 종료 시간을 제거한다.
• 현재 강의가 종료하는 시간을 힙에 push() 한다.

✍ 코드

# 1374 강의실 <골드 5>
from sys import stdin
from heapq import heappush, heappop
N = int(stdin.readline())
lectures = []
for _ in range(N):
    num, start, end = map(int,stdin.readline().split())
    lectures.append((start,end))
lectures.sort() # 강의 시작 시간을 기준으로 오름차순으로 정렬
H = [lectures[0][1]] # 힙에 가장 빨리 시작하는 강의의 종료 시간을 push()
for i in range(1,N):
    start, end = lectures[i]
    # 힙에 가장 빨리 종료하는 강의의 시간이 현재 강의의 시작 시간과 같거나 작다면
    # 힙에 가장 빨리 종료하는 강의의 시간 pop()
    if start >= H[0]: heappop(H) 
    heappush(H,end) 
print(len(H))