파이썬 백준 1931 회의실 배정

import sys
input = sys.stdin.readline
 
n = int(input())
l = []
for i in range(n) : 
    l.append(list(map(int, input().split())))
l.sort(key = lambda x : x[0])
l.sort(key = lambda x : x[1])
now = 0
count = 0
for start, end in l : 
    if start >= now : 
        count = count + 1
        now = end
print(count)

IDEA

회의들을 종료점이 빠른 순서대로 (=일찍 끝나는 순서대로) 정렬한다.

시간 now는 0에서 시작해서, 지금 회의실을 쓴 회의가 끝나면 그 회의의 end로 갱신된다.

now보다 늦게 시작하는 회의(= 회의실을 쓸 수 있는 회의)를 리스트에서 순서대로 찾아 회의실에 넣는다.

리스트가 일찍 끝나는 순으로 정렬되었으므로 매 선택마다 이렇게 찾은 회의가 회의실을 쓸 수 있는 회의 중에서는 가장 일찍 끝나는 회의이고, 이 선택의 반복이 가장 효율적인 사용이 된다.