[백준] 11000번 > 강의실 배정

www.acmicpc.net/problem/11000

11000번: 강의실 배정

문제

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

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

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

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

입력

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

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

출력

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

 

---

풀이

이 문제는 최소힙을 사용하면 간단하게 해결할 수 있다.

먼저 입력값을 정렬해주는데 lambda식을 이용하여 수업시작 시간을 기준으로 동일한 것이 있다면 수업 종료 시간을 기준으로 정렬해준다.

 

이렇게 정렬을 수행한 후에 리스트의 첫 값은 가장 수업시간 빠른 수업이므로 무조건 강의실을 하나 잡아줘야한다. 그래서 강의실 count의 시작은 1이고, 힙에 첫번째 수업의 종료시간을 넣는다.

 

종료시간을 넣는 이유는 연강을 할 수 있는지를 검사하기 위해서이다. 

 

이제 리스트 인덱스 1번부터 끝까지 for문을 통해 검사하는데 최소힙의 0번째 원소와 해당 수업의 시작 시간을 비교하여 만약 해당 수업의 시작시간이 같거나 크다면 연강을 할 수 있으므로 힙의 0번째 원소를 pop해주고 해당 수업의 종료시간을 다시 힙에 push해주면 된다.

 

만약 작다면 이것은 연강이 불가능하므로 강의실을 따로 하나 배정해줘야하므로 count를 +1해주고 마찬가지로 힙에 수업 종료시간을 push해주면 된다.

 

import sys
import heapq
input = sys.stdin.readline
n = int(input())
lectures = [list(map(int, input().split())) for _ in range(n)]
lectures = sorted(lectures, key=lambda x: (x[0], x[1]))
count = 1
queue = []
heapq.heappush(queue, lectures[0][1])
for i in range(1, n):
    if lectures[i][0] >= queue[0]:
        heapq.heappop(queue)
        heapq.heappush(queue, lectures[i][1])
    else:
        count += 1
        heapq.heappush(queue, lectures[i][1])
print(count)