[Baekjoon]백준 1931 회의실 배정(골드 5) - Python

문제설명

예제와 힌트

문제를 살펴보면 여러가지 회의 일정들이 주어지고, 그 일정을 보고 최대한 많은 회의를 할 수 있는 시간표를 짜야한다

그래서 처음에 들었던 생각이 모든 경우의 수를 확인하고, 그 중에서 가장 큰 값을 출력하는 것이 간단하긴하지만

중첩 for문을 사용하면 시간복잡도 측면에서 상당히 불리하다는 생각이 들었다 

회의 기간을 짧은 것을 기준으로 정렬을 하게 되면 시작시간, 종료시간이 각각 달라서

순서가 이상할 것 같다는 생각이 들어서 시작 시간 또는 종료 시간을 기준으로 sort하여 카운트 하는 방법을 생각했다

 

시작 시간으로 정렬하다보니 더 짧은 시간으로 회의가 진행되는 경우를 놓치게 되는 것을 확인하였다

예를 들어 (0, 6), (1, 3), (4, 5) 와 같은 경우가 있을 때 시작 시간을 기준으로 정렬하면

(0, 6)을 선택하게 되기 때문에 종료 시간으로 정렬하는 것이 최적의 방법이라고 생각하였다

일단, 일정 시간표를 튜플로 입력을 받도록 코드를 작성하였다

이후에 sort와 lambda를 활용하여 종료시간을 기준으로 정렬해주었다

해당 리스트의 가장 첫번째 값에 가장 늦은 종료시간이 저장되어있기 때문에 이 시간을 탐색 시작 기준으로 잡고,

기준으로 잡은 시간은 무조건 포함되기 때문에 cnt 변수는 1로 초기화를 해준다

마지막으로 for문을 통해 현재 시작 시간이 이전에 선택된 종료 시간보다 크거나 같다면

해당 시간표를 변수에 저장하고, cnt 를 +1해주며 확인해주면 된다

import sys

num = int(input())
time = []
for i in range(num):
    start_time, end_time = map(int, sys.stdin.readline().split())
    time.append((start_time, end_time))
        
time.sort(key=lambda x : (x[1], x[0]))
# print(time)
cnt = 1
fin = time[0][1]
for i in range(1, num):
    if time[i][0] >= fin:
        fin = time[i][1]
        cnt += 1
        
print(cnt)