Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 11000 강의실 배정
백준 11000 강의실 배정
문제
수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.
김종혜 선생님 한테는 S에 시작해서 T에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해 모든 수업을 가능하게 해야 한다.
참고로 수업이 끝난 직후 다음 수업을 시작할 수 있다.
강의실 개수를 출력하라
입력
- 첫째 줄: N
- 둘째 줄: 수업 시작 시간 S와 끝나는 시간 T
출력
강의실 개수
해결 방식
그리디 알고리즘
- 입력받은 시간을 시작 시간 기준 정렬
- 처음 시작하는 회의를 queue에 추가
- 두번째 회의가 시작하는 시간과 첫번째 회의가 끝나는 시간 비교
- 두번째 회의가 시작하는 시간 < 첫번째 회의가 끝나는 시간: 새 회의실 생성
- 두번째 회의가 시작하는 시간 > 첫번째 회의가 끝나는 시간: 기존 회의실 이용
코드
import heapq
import sys
input = sys.stdin.readline
n = int(input())
classTime = [list(map(int, input().split())) for _ in range(n)]
classTime.sort() # 시작 시간 기준 정렬
classRoom = []
heapq.heappush(classRoom, classTime[0][1])
for i in range(1, n):
if classTime[i][0] < classRoom[0]:
heapq.heappush(classRoom, classTime[i][1])
else:
heapq.heappop(classRoom)
heapq.heappush(classRoom, classTime[i][1])
print(len(classRoom))
