[백준] 11000:강의실 배정
우선순위 큐
문제 해석 :"수업이 끝난 직후에 다음 수업을 시작할 수 있다."
->
현재 수업이 끝나지 않은 채 다음 수업이 시작된다면 강의실 한개가 더 필요하다
즉, 이 문제는 현재 수업이 끝나는 시간과 다음 수업이 시작하는 시간이 중요하겠고,
현재 수업 시간이 끝나는 시간보다 다음 수업이 시작하는 시간이 빠르면 강의실 하나를 더 (사용)하고 ,
늦거나 같다면, 현재 수업하는 강의실을 사용하면 된다.(교체)
그래서 우선 순위 큐를 두어 현재 상황에서 가장 먼저 끝나는 강의실을 맨 앞에 두고, 다음 수업의 종료 시간을 힙에 넣어주면 된다. 더 자세한 설명은 코드를 보자
import sys
import heapq
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
start, end = map(int, input().split())
lst.append((start, end))
# 시작 시간이 빠른 순서대로 정렬 (맨 처음 시작하는 강의의 종료 시간이 중요하기 때문이다)
lst.sort(key=lambda x:x[0])
answer = []
# 맨 처음 강의의 종료 시간을 추가
answer.append(lst[0][1])
for i in range(1, n):
# 현재 강의의 종료 시간이 다음 강의의 시작 시간 보다 느리면 강의실 추가
if answer[0] > lst[i][0]:
heapq.heappush(answer, lst[i][1])
else:
# 현재 강의의 종료 시간이 다음 강의의 시작 시간과 같거나 빠르면 현재 강의수업이 끝나고 , 현재 강의실 쓰면 됨
heapq.heappop(answer)
heapq.heappush(answer, lst[i][1])
# 강의실 개수 출력
print(len(answer))
Author And Source
이 문제에 관하여([백준] 11000:강의실 배정), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@jinii/백준-11000강의실-배정
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
문제 해석 :"수업이 끝난 직후에 다음 수업을 시작할 수 있다."
->
현재 수업이 끝나지 않은 채 다음 수업이 시작된다면 강의실 한개가 더 필요하다
즉, 이 문제는 현재 수업이 끝나는 시간과 다음 수업이 시작하는 시간이 중요하겠고,
현재 수업 시간이 끝나는 시간보다 다음 수업이 시작하는 시간이 빠르면 강의실 하나를 더 (사용)하고 ,
늦거나 같다면, 현재 수업하는 강의실을 사용하면 된다.(교체)
그래서 우선 순위 큐를 두어 현재 상황에서 가장 먼저 끝나는 강의실을 맨 앞에 두고, 다음 수업의 종료 시간을 힙에 넣어주면 된다. 더 자세한 설명은 코드를 보자
import sys
import heapq
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
start, end = map(int, input().split())
lst.append((start, end))
# 시작 시간이 빠른 순서대로 정렬 (맨 처음 시작하는 강의의 종료 시간이 중요하기 때문이다)
lst.sort(key=lambda x:x[0])
answer = []
# 맨 처음 강의의 종료 시간을 추가
answer.append(lst[0][1])
for i in range(1, n):
# 현재 강의의 종료 시간이 다음 강의의 시작 시간 보다 느리면 강의실 추가
if answer[0] > lst[i][0]:
heapq.heappush(answer, lst[i][1])
else:
# 현재 강의의 종료 시간이 다음 강의의 시작 시간과 같거나 빠르면 현재 강의수업이 끝나고 , 현재 강의실 쓰면 됨
heapq.heappop(answer)
heapq.heappush(answer, lst[i][1])
# 강의실 개수 출력
print(len(answer))
Author And Source
이 문제에 관하여([백준] 11000:강의실 배정), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jinii/백준-11000강의실-배정저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)