❓1931번 : 회의실 배정
📈 문제 요약
한 개의 회의실을 사용하고자 하는 N개의 회의에 대하여 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있을 때, 각 회의가 겹치지 않게 회의실을 사용할 수 있는 회의의 최대 개수를 찾으면 되는 문제
🤨 접근법
그리디 알고리즘 문제를 풀이할 때 고려해야 하는 점 중 가장 중요한 것은 특정 시점의 최적의 해답을 찾는 것이다. 이러한 측면에서 최대한 많은 회의를 배치시킬 수 있도록 하기 위해서는 이른 종료 시간의 회의를 선택해야 한다. 그렇다면 특정 시점의 최적의 해답은 가장 이른 종료시간의 회의를 선택하는 것이다.
이를 위해 입력받은 스케쥴들을 종료시간에 대해 정렬해서 활용해야 한다. 그리고 동일 종료 시간의 회의에 대해서는 더 이른 시간의 회의를 선택하는 것이 가장 최적의 해답일 것이다. 즉, 정렬된 회의 리스트를 순회하면서 이전 회의 종료 시간보다 같거나 큰 시작 시간을 가지는 회의를 다음으로 선택한다.
🔡 코드
import sys
input = sys.stdin.readline
N = int(input())
schedule = sorted([list(map(int, input().rstrip().split())) for _ in range(N)], key = lambda x : (x[1], x[0]))
tmp = 0
result = 0
for start, end in schedule:
if start >= tmp:
result += 1
tmp = end
print(result)회의들을 종료시간 → 시작시간 기준으로 정렬하기 위해 sorted 함수의 key 인자를 활용했다. 다음과 같이 key 인자에 lambda x : (x[1], x[0])을 주게 되면 다차원의 자료구조를 원소를 갖는 리스트에서 lambda 식의 튜플에 주어진 인자의 차원 기준으로 우선 정렬하게 된다.
즉, schedule 리스트에서 [시작시간, 종료시간]을 원소로 가지므로, schedule[0]은 시작 시간, schedule[1]은 종료 시간을 의미한다. 따라서 종료 시간, 시작 시간 순으로 우선순위를 지정하여 정렬을 수행하게 된다.
정렬된 회의 리스트를 순회하면서 이전 회의 종료 시간보다 같거나 큰 시작 시간을 가지는 회의를 다음으로 선택한다.
for start, end in schedule:
if start >= tmp: # 이번 회의 시작 시간이 이전 회의 종료 시간 보다 같거나 큰 경우
result += 1
tmp = end # tmp에 회의 종료 시간 저장이 과정에서 회의를 고려할 때마다 result를 늘려주고, 순회가 끝나면 최종적으로 result를 출력한다.
