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

문제 링크

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

1931번: 회의실 배정

 

문제 풀이 

이 문제의 포인트는 회의가 끝나는 시간을 우선순위로 정렬해야 한다는 것이다. 회의가 빨리 끝날수록 다음에 시작할 수 있는 회의가 많기 때문이다. 

1. 회의 끝나는 시간을 우선순위 정렬
2. 이전 회의 끝나는 시간 <= 다음 회의 시작 시간 : cnt++, prev_end 업데이트

 

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
time_table = [list(map(int, input().split())) for _ in range(n)]
time_table.sort(key = lambda x : (x[1], x[0])) # 끝나는 시간 우선순위 정렬
cnt, prev_end = 0, 0

# 다음 회의 시작 시간이 이전 회의 끝나는 시간보다 늦게 시작한다면 cnt++
for start, end in time_table :
    if prev_end <= start :
        cnt += 1
        prev_end = end # 이전 회의 끝나는 시간 업데이트

print(cnt)