백준 1931 - 회의실 배정 [Python]

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

---

풀이 과정

회의의 시작 시간과 끝나는 시간이 주어질 때, 회의가 겹치지 않으면서 가장 많은 회의를 진행하는 경우를 구하는 문제이다.

 

가능한 많은 회의를 진행하려면 회의의 종료시간이 빠른 순서대로 회의를 진행하면 된다. 회의의 종료시간이 같은 두 개의 회의가 존재할 때는 어떻게 처리해야 할까?

(9, 10), (10, 10) 두 입력이 들어왔다 가정하자. 여기서 (10, 10)을 먼저 처리하면 (9, 10)이 그리디로 처리되지 않는다. 따라서 종료시간이 빠른 순서대로 처리하되, 종료시간이 같은 회의는 시작시간이 더 빠른 회의가 우선으로 배정되도록 처리해야 한다.

---

소스 코드

import sys

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

for i in range(N):
    start, end = map(int, sys.stdin.readline().split())
    meeting.append([start, end])

meeting.sort(key=lambda x: (x[1], x[0]))

answer = 1
end = meeting[0][1]

for i in range(1, N):
    if meeting[i][0] >= end:
        answer += 1
        end = meeting[i][1]

print(answer)