BOJ 11000 : 강의실 배정 (Python)

문제

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

11000번: 강의실 배정

 

 

코드

import sys
import heapq
n = int(sys.stdin.readline())

array = []

for i in range(n):
    array.append(list(map(int, sys.stdin.readline().split())))

array.sort()

room = []
heapq.heappush(room,array[0][1])

for i in range(1,n):
    if array[i][0] < room[0]:
        heapq.heappush(room, array[i][1])

    else:
        heapq.heappop(room)
        heapq.heappush(room, array[i][1])
        
print(len(room))

 

 

풀이

처음엔 리스트로 무작정 풀다가 시간초과로 인해 해결하지 못했다.

우선 순위 큐를 이용해서 푸니 문제가 해결되었다!

 

먼저 강의 시작, 종료 시간을 array 라는 배열 담아서 2차원 배열로 만들어준다.

→ 2차원 배열에서 sort를 하면 0번째 인덱스를 기준으로 오름차순 정렬을 먼저 하는 것이 디폴트인 것 같다.

 

ex. array = [[1,5], [3,2], [3,1], [5,1], [1,2]] 에서 array.sort()를 실행하면 array = [[1,2], [1,5], [3,1], [3,2], [5,1]]

 

room 이라는 힙을 만들어서 먼저 첫번째 강의의 종료 시간을 넣는다.

 

for 문 내에서는,

i 번째 강의의 시작 시간이 현재 힙 (room) 내에 있는 수업의 종료 시간보다 이른 경우에는 새로운 강의실을 만든다는 의미로, 힙에 i 번째 강의의 종료 시간을 추가 한다.

 

i 번째 강의의 시작 시간이 현재 힙 (room) 내에 있는 수업의 종료 시간보다 나중인 경우에는 같은 강의실에서 수업을 진행한다는 의미로, 힙에 있던 수업의 종료 시간을 없앤 뒤 i 번째 강의의 종료 시간을 넣어 준다. 

 

if array[i][0] < room[0]:
        heapq.heappush(room, array[i][1])

힙 내에서는 작은 순으로 정렬 돼 있으므로 room[0] 과 비교하기만 하면 된다. 

 

 

 

 

 

 

 

시간초과한 코드

틀린 부분은 없을 것 같긴 하다.. (모름)

import sys
n = int(sys.stdin.readline())

array = []

array.append(list(map(int, sys.stdin.readline().split())))

room = 1

for i in range(1,n):
    start, end = map(int, sys.stdin.readline().split())
    check = 0
    for j in range(len(array)):
        check += 1
        if array[j][1] <= start:
            array[j][0] = start
            array[j][1] = end
            break
    if check != i:
        room += 1
        array.append([start,end])
        
print(len(array))