[python/파이썬] 백준 11000 강의실 배정

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

예제 입력 1 복사

3
1 3
2 4
3 5

예제 출력 1 복사

2

 

 

[문제 풀이]

 

우선 time리스트에 각 강의의 시작시간과 종료시간을 저장한다.

후에 시작시간을 기준으로 정렬한다.

 

time = sorted(time, key=lambda x: x [0])

time의 경우

[ [s0, e0], [s1, e1], [s2, e2],....., ] 이런 식으로 구성되어 있다.

람다 함수를 사용해서 x [0] 즉 시작 시간을 기준으로 하여 정렬할 수 있다.

 

먼저 시작되는 강의를 우선 배정하는 것이 유리하기 때문에 시작시간을 기준으로 오름차순 정렬을 하면

가장 첫 번째에 위치하는 강의가 가장 먼저 시작될 강의이다.

 

따라서 heap에 0번째 강의의 종료시간인 time [0][1]을 저장한다.

heapq는 최소 힙을 지원하므로 가장 첫 번째 요소는 가장 작은 값이 된다.

 

for문을 보면

만약 가장 빨리 끝나는 강의(heap [0])보다도 i번째 강의의 시작 시간이 더 빠르다면,

새로운 강의실을 하나 더 배정해야 할 것이다.

따라서 heap에 i번째 강의의 종료시간을 저장한다.

 

i번째 강의가 지금 진행되고 있는 강의들이 끝나고 해당 강의실에서 진행될 수 있다면, 강의실의 개수는 변하지 않으므로

pop을 하고 i번째 강의의 종료시간을 저장한다.

 

 

[소스 코드]

import sys
import heapq

input = sys.stdin.readline

n = int(input())
time = [] #시작시간과 종료시간들을 저장할 리스트
heap = [] 

for i in range(n):
    start, end = map(int, input().split())
    time.append([start,end])

time = sorted(time, key=lambda x: x[0]) #시작시간을 기준으로 오름차순으로 정렬

heapq.heappush(heap, time[0][1] ) #첫 번째 강의가 끝나는 시간을 정렬

for i in range(1,n):#첫 번째 강의가 저장된 상태니 두번째 강의부터
    if heap[0] > time[i][0]: #진행 중인 강의중에 가장 빨리 끝나는 시간보다 i번째강의의 시작시간이 더 빠르다면
        heapq.heappush(heap,time[i][1]) #강의실을 하나 추가한다(i번째 강의의 종료시간을 저장)
    else:
        heapq.heappop(heap) #진행중인 강의 다음에 i번째 강의가 진행될 수 있다면 해당 강의실의 종료시간을 i번째 강의의 종료시간으로
        heapq.heappush(heap,time[i][1])
print(len(heap))