백준 11000번 강의실 배정

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #자료구조 #다이나믹 프로그래밍 #정렬 #우선순위큐

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

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

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

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

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

---

입력

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

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

---

출력

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

---

예제 입출력 1

입력

3
1 3
2 4
3 5

출력

2

---

코드(파이썬)

import sys
import heapq


n = int(sys.stdin.readline())
lectures = sorted([tuple(map(int, sys.stdin.readline().split())) for _ in range(n)])

dp = [lectures[0][1]]

for s, t in lectures[1:]:
    if s >= dp[0]:
        heapq.heappop(dp)
        heapq.heappush(dp, t)
    else:
        heapq.heappush(dp, t)

print(len(dp))

---

특이사항

• 풀이과정
  • 강의를 시작시각 순서로 정렬
  • dp 힙에 첫 강의의 종료시각 저장
  • 현재강의 시작시각 s와 dp 힙의 가장 작은 종료시각 비교
    • s가 더 크다면 종료 이후 시작 가능하므로 dp 힙에서 가장 작은 종료시각 제거 후 현재강의 종료시각을 dp 힙에 저장
    • s가 더 작다면 dp 힙에 추가
• 강의를 (가) 시작시각 순서로 오름차순 정렬 vs (나) 종료시각 순서로 오름차순 정렬
  • 예제 데이터

    4
    1 2
    1 4
    2 6
    4 5
    

  • 
  • (가)
    • 정렬 직후 강의 리스트: [(1,2) (1,4) (2,6) (4,5)]
    • 진행 중 dp 힙 변화: [2] -> [2, 4] -> [4, 6] -> [5, 6]
  • (나)
    • 정렬 직후 강의 리스트: [(1,2) (1,4) (4,5) (2,6)]
    • 진행 중 dp 힙 변화: [2] -> [2, 4] -> [4, 5] -> [4, 5, 6]
  • 종료시각 순서로 정렬하는 경우 (나)와 같은 상황이 발생함

---

참고문헌

-