[백준] [파이썬] [그리디] [힙큐] 11000번: 강의실 배정

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

11000번: 강의실 배정 문제 보러 가기

11000번: 강의실 배정

 

 

1931번: 회의실 배정 문제와 다른 점을 알아보자 

문제

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

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

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

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

입력

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

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ S_i < T_i ≤ 10^9)

출력

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

예제 입력 1

3
1 3
2 4
3 5

예제 출력 1

2

---

문제를 요약하자면 주어진 수업들을 모두 수행하기 위해 몇개의 강의실이 필요한지 구하는 것이다.

 

 

이 문제는 무조건 힙큐를 써야한다.

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.

 

힙 특성 : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다

• 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

 

이러한 속성으로 인해 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 되고 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

이때 키값의 대소 관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 정해지지 않는다.

 

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

https://littlefoxdiary.tistory.com/3

 

요약: 

파이썬의 heapq 모듈은 최소 힙(min-heap)을 구현

최소 힙에서 항상 가장 작은 값이 루트에 위치하며, 이를 리스트로 표현할 때는 가장 왼쪽에 위치

즉, 힙에서 가장 작은 값은 리스트의 첫 번째 요소(heap[0])가 됩니다.

 

 

그럼 이제 그림과 함께 문제의 풀이 과정을 살펴본다. 

1. 수업 시작 시간을 기준으로 오름차순 정렬 

2. 제일 빨리 시작하는 수업1의 종료 시간을 우선순위 큐에 삽입

 

3. 수업1 다음으로 빨리 시작하는 수업2의 시작 시간 2는 수업1의 종료 시간 3보다 작으므로 강의실 한개가 더 필요하다. 따라서 수업2의 종료 시간을 우선순위 큐에 삽입한다.

4. 수업2 다음으로 빨리 시작하는 수업3의 시작 시간 3은 수업1의 종료 시간 3이랑 같으므로 강의실을 이어서 사용할 수 있다. 따라서 추가적인 강의실이 필요하지 않는다. 수업1의 종료 시간을 삭제하고 수업3의 종료 시간을 우선순위 큐에 삽입한다.

 

 

---

 

정답

 

import heapq as hq 
import sys

sys.stdin=open('input.txt', 'r')


def solution(lectures):
    
    # 강의실 시작을 기준으로 정렬
    lectures.sort(key=lambda x : (x[0],x[1]))

    room = []
    # 가장 빠른시간의 강의(첫수업)의 끝나는 시간을 넣기 
    hq.heappush(room, lectures[0][1])
    
    for start,end in lectures[1:]:      # 그 다음수업부터 살펴보기
        if start < room[0]:             # 현재 수업 시작 시간이 첫 수업 끝나는 시간보다 일찍 시작하면
            hq.heappush(room, end)      # 현재 수업 끝나는 시간을 넣어줌 (즉 강의실 추가 배정)
        else:
            hq.heappop(room)            # 강의실 수업이 끝나고 이어서 수업이 가능하면 강의실 끝나는 시간 하나 빼고 
            hq.heappush(room, end)      # 가장 늦은 끝나는 시간 넣어주기 
            
    return len(room)


if __name__=="__main__":
    N = int(input())

    lectures = []
    
    for i in range(N):
        start, end = map(int, input().split())
        lectures.append([start, end])
    
    ans = solution(lectures) 
    print(ans)

---