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

문제

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

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

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

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

입력

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

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

출력

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

풀이

1931번 https://www.acmicpc.net/problem/1931
회의실과 비슷한 문제인줄 알고 껌이네~ 하면서 가벼운 맘으로 풀었다.

근데 저건 한 회의실에서 할 수 있는 강의의 최대를 구하는 것이고

이 문제는 강의실의 최소 개수를 묻는 것..

열심히 짱구를 굴려봤지만
역시나 cctv 문제때 처럼 거의 비슷하게는 접근했는데 마무리를 못지었다ㅠ

접근 방법

1931과는 반대로
시작시간을 기준으로 정렬한다.

그리고 classroom이라는 우선순위 큐를 활용한다.

이때 classroom은 끝나는 시간을 기준으로 정렬하는게 포인트

첫번째 수업을 classroom에 넣는다 무조건 1개의 강의실은 필요하니까

그 다음으로 아직 배정 안된 수업의 시작시간과

classroom 의 가장 일찍 끝나는 수업의 종료시간을 비교한다.

1. 만약 가장 일찍 끝나는 수업의 종료시간보다 아직 배정x 수업의 시작시간이 일찍이라면

   새로운 강의실을 개설한다
   -> classroom에 배정 안된 수업을 push(우선 순위 큐를 활용하여 알아서 종료시간을 기준으로 정렬되게)

2. 가장 일찍 끝나는 수업의 종료시간보다 아직 배정x 수업의 시작시간이 늦게라면
   새로 강의실을 개설할 필요없고 기존 강의실을 활용한다
   -> classroom에서 pop하고 배정 안된 수업을 push
   (pop 했으므로 강의실 개수는 변함이 없으므로 push를 했다고 개설한게 아니다)

정답으로 개설 되어있는 classroom의 개수를 보면 된다.

소스코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())
stList = []
for _ in range(n):
    stList.append(list(map(int, input().split())))
stList.sort(key=lambda x: x[0])  # 시작시간을 오름차순으로
start, end = heapq.heappop(stList)
classroom = []  # 종료시간을 오름 차순으로 종료시간만 저장
classroom.append(end)
while stList:
    start, end = heapq.heappop(stList)  # 두번째로 시작하는 시간부터 꺼냄
    if start < classroom[0]:  # 배정안된 수업의 시작이 가장 일찍끝나는 수업의 끝보다 작으면
        heapq.heappush(classroom, end)  # 끝나는 시간 추가하고 정렬(수업 개설)
    else:  # 배정안된 수업의 시작이 가장 일찍끝나는 수업의 끝보다 늦게 시작하면
        heapq.heappop(classroom)  # 가장 일찍 끝나는 수업 뺴고
        heapq.heappush(classroom, end)  # 그 교실을 이어감


print(len(classroom))