[백준] 11000 파이썬(python) : 강의실 배정

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

11000번: 강의실 배정

 

 

처음에 문제를 잘못 이해했다. 같은 강의실에서 다른 강의실 할 수 있는 줄 모르고 내 학기중 수업 들었던것만 생각해서 수업이 끝나면 바로 다른곳으로 이동해야하는 줄 알고 이전 수업 끝나는 시간 t가 다음 수업 시작하는 시간 s가 같거나 작으면 heap에 추가해주는줄 알았다. 그래서 처음 제출은 실패. 그렇게 이해하면 우선순위 큐를 사용할 일도 없다. 뭔가 이상해서 블로그를 찾아보니 수업시간이 겹치는 강의가 생기면 그때 강의실을 추가해주는거였다. 설정상 수업시간이 겹쳐도 교수님이 슈퍼맨이어셔서 왔다갔다 하면서 강의할 수 있다는 것이다. 

 

import sys, heapq
n = int(sys.stdin.readline())
heap = []
class_room = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
class_room.sort() #1
heapq.heappush(heap, class_room[0][1]) #2
for i in range(1, len(class_room)): #3
    if heap[0] > class_room[i][0]: #4
        heapq.heappush(heap, class_room[i][1])
    else: #5
        heapq.heappop(heap)
        heapq.heappush(heap, class_room[i][1])
print(len(heap)) #6

 

#1 : 가장 빠른 시작 시간부터 시작해야하므로 오름차순 정렬

#2 : 처음에 heap 자료구조에 첫번째 강의 끝나는 시간 삽입

#3 : 그 다음은 1부터 끝까지 반복

#4 : 다른 수업 시작 시간이 heap에 들어있는 이전 수업 끝나는 시간보다 작다면 즉, 2개의 수업시간이 겹치면 heap에 수업 끝나는 시간 추가

#5 : 같거나 더 크다면 heap에 있는 끝나는 시간 빼주고 새로운 수업의 끝나는 시간 삽입 즉, 교실을 이동할 필요없이 같은 교실에서 이어서 수업이 가능

#6 : 들어있는 끝나는 숫자의 개수만큼이 중복으로 겹친 시간이고 강의실이 추가로 필요한 개수가 된다

 

#4, #5가 실행되는 과정

1931번 문제 회의실 배정이랑 이름이 비슷하다(https://hgk5722.tistory.com/71)