[백준] 회의실 배정

www.acmicpc.net/problem/1931

1931번: 회의실 배정

---

문제설명

1. n개의 회의 스케줄이 주어진다.

2. 각 스케줄에는 (시작시간, 종료시간)이 주어진다.

3. 가장 많은 회의를 진행했을 때 개수는?

4. 단, 회의 시간이 종료되자마자 회의가 시작될 수 있으며, 회의시작 시간과 종료시간이 같을 수 있다.

 

문제 특징

- 회의가 빨리 끝나면 더 많은 회의를 할 수 있다.

하지만 단순히 회의 종료시간을 기준으로 오름차순을 하게 되면 반례에 걸리게 된다.

예를 들어, [5, 5], [5, 5], [4, 5]가 스케줄로 주어진다고 하자.

 

그렇다면 우리가 예상하는 답은 [4, 5], [5, 5], [5, 5]이다.

하지만 만약 회의 시작시간이 내림차순으로 되어 있다면 [5, 5], [5, 5], [4, 5]가 출력이 된다.

따라서 "종료시간(오름차순) -> 시작시간(오름차순)"으로 정렬이 이뤄져야 한다.

 

코드

import sys
import heapq
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n = int(input())
heap = []
for _ in range(n):
    s, e = map(int, input().split())
    heapq.heappush(heap, (e, s))

cnt = 0
before_e = 0
while heap:
    e, s = heapq.heappop(heap)
    if s >= before_e:
        before_e = e
        cnt += 1
print(cnt)