1931번 - 회의실 배정

문제

1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

풀이

최대한 많은 회의실 예약을 받으려면 회의시간이 짧고 일찍 끝나는 회의를 받으면 된다. 우선순위 큐에 회의가 끝나는 시간, 시작하는 시간 순으로 넣어주면 된다.

import heapq
import sys

input = sys.stdin.readline

N = int(input().rstrip())
heap = []

for _ in range(N):
    start,end = map(int,input().split())
    heapq.heappush(heap,(end,start))

answer = 0
now = 0

while heap:
    end,start = heapq.heappop(heap)
    if start >= now:
        answer += 1
        now = end

print(answer)