[Python/백준] 11000 강의실 배정

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

11000번: 강의실 배정

<문제 해설>

그리디 문제이다. 

우선 수업을 시작하는 시간을 기준으로 오름차순 정렬해준다. 그후 우선순위큐를 만들어 주고 종료시간을 넣어주며 수업 시작시간을 순서대로 비교하면 된다. 마지막으로 출력은 heapq안에 남아있는 것들의 개수를 출력해주면 된다.

우선순위큐는 파이썬 내장함수인 heapq를 사용했다.

자세한것은 예시를 들어서 설명하겠다.

<예시>

위에보이는 강의 예시를 입력값으로 하겠다.

예시의 경우 위에 보이는 사진처럼 3개의 강의실만 사용해서 모든 수업을 할 수 있다.

그렇다면 알고리즘 적으로도 맞는지 확인해보자.

윗 사진은 예시를 시작시간 기준으로 정렬한뒤 1번 강의부터 차례대로 계산했을 때 room이라는 이름의 우선순위 큐안에서 일어나는 일을 표로 만들었다.

1번 강의를 넣었을 땐 1번 강의가 끝나는 시간인 3이 room안에 남아있다.

4번 강의를 넣었을 땐 room안에 있는 시간중 가장 작은 시간인 3이 4번 강의의 시작 시간보다 큼으로 새로운 강의실에서 시작해 room안에 5를 넣어준다.

2번 강의를 넣었을 땐 room안에 있는 시간중 가장 작은 시간인 3이 2번 강의의 시작 시간보다 큼으로 새로운 강의실에서 시작해 room안에 4를 넣어준다.

3번 강의를 넣었을 땐 room안에 있는 시간중 가장 작은 시간인 3이 3번 강의의 시작 시간과 같음으로 기존 강의실에서 할수 있기에 room안의 3을 5로 바꿔준다.

이렇게 최종적으로 남은 4,5,5 3개의 강의실이 답이된다.

<코드>

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

time = []
for i in range(N):
    time.append(list(map(int,sys.stdin.readline().split())))

time.sort()

room = [time[0][1]]

for i in range(1,N):
    if time[i][0] >= room[0]:
        heapq.heappop(room)
    heapq.heappush(room, time[i][1])
        
print(len(room))

<코드 설명>

import heapq //heapq함수를 불러오기
import sys //sys함수를 불러오기
N = int(sys.stdin.readline()) //N값 정수로 받아오기

time = [] //강의 시간을 담을 배열
for i in range(N): //N만큼 반복
    time.append(list(map(int,sys.stdin.readline().split()))) //시간 받아와서 time 배열에 저장하기

time.sort()  //오름차순으로 정렬하기

room = [time[0][1]] //room heapq에 가장 빨리시작하고 빨리 끝나는 강의의 끝나는 시간값 넣어주기

for i in range(1,N): //2번째 작은 강의부터 정부
    if time[i][0] >= room[0]: //강의 시작 시간이 강의 끝나는 시간보다 크거나 같으면
        heapq.heappop(room) //기존 시간이 적혀있던 강의 지우고
    heapq.heappush(room, time[i][1]) //강의의 끝나는 시간 넣어주기
        
print(len(room)) //강의실의 개수 출력해주기