[Baekjoon/Python] 1931번: 회의실 배정(Greedy)

# Baekjoon 1931번: 회의실 배정
import sys
input = sys.stdin.readline

N = int(input())
room = []

for i in range(N):
    start, end = map(int, input().split())
    room.append((start, end))


room = sorted(room, key = lambda x: x[0])
room = sorted(room, key = lambda x: x[1])
room_max = 0
present_end = 0

for s, e in room:
    if present_end <= s:
        present_end = e
        room_max += 1

print(room_max)

그리디 알고리즘은 매 순간 최적해를 찾아가는 알고리즘이다. 회의실 배정 문제에서는 회의의 끝나는 시간이 중요하기 때문에 먼저 끝나는 시간으로 정렬해준다. 하지만 이때 끝나는 시간으로 정렬하기 전에 시작 시간으로 먼저 정렬을 해줘야 하는데, 문제에서 회의의 시작 시간과 끝나는 시간이 같은 경우도 있다 했으므로 이를 고려해야한다. 예를 들어 6 10, 10 10 시간 때에 회의가 있다고 했을 때 10, 10 -> 6, 10 으로 정렬이 되면 6, 10을 카운트하지 못하기에 고려해야 한다.