[BOJ] 1931 : 회의실배정 (Python3)

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

풀이

회의시간을 배열로 받아 끝나는 시간이 이른 것부터 정렬한다.
일찍 끝날수록 다른 회의를 많이 할 수 있기 때문이다.
다만 끝나는 시간이 같은 경우를 위해 시작 시간도 오름차순으로 정렬해야 한다.
(2, 2)
(1, 2)
처럼 회의가 배정되어있을 경우, 해당 순서로는 답이 1로 나오지만 순서가 바뀌면 2개 회의를 모두 열 수 있다.
이처럼 정렬한 뒤, 시작 시간이 채택한 회의 시간의 끝 시간보다 크거나 같은 경우 cnt += 1을 한다.
반복문이 끝나면 cnt를 출력한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
times = [list((map(int, input().strip().split()))) for _ in range(n)]
times.sort(key=lambda x: [x[1], x[0]])

end_time = 0
cnt = 0

for x, y in times:
    if x >= end_time:
        cnt += 1
        end_time = y

print(cnt)