문제

김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다.

제약 사항

• 1 ≤ N ≤ $10^6$ 인 정수
• 1 ≤ $S_i$ ＜ $F_i$ ≤ $10^9$

입력

첫 번째 줄에 강의 개수 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 강의의 시작 시간 $S_i$와 종료 시간 $F_i$가 주어진다.

출력

첫 번째 줄에 최대 강의 수를 출력하라.

풀이

아이디어

• 강의실을 최대한 많이 배정하는 이 유형은 "끝나는 시간이 제일 빠른" 아이들을 계속 고르는 문제이다.
• 따라서, 끝나는 시간을 우선순위로 한 우선순위 큐(최소 힙)을 만들어서 다 넣고, 하나씩 빼가면서 마지막 강의가 끝나는 시간보다 시작시간이 더 늦은 것을 배정하는 문제이다.

코드

import sys
from heapq import heappush, heappop

N = int(sys.stdin.readline())
heap = []

for i in range(N):
  start, end = list(map(int, sys.stdin.readline().split()))
  heappush(heap, (end, start))

count = 0
cur_end = 0
while heap:
  e, s = heappop(heap)
  if s >= cur_end:
    cur_end = e
    count += 1

print(count)