풀이
import sys
input = sys.stdin.readline
n = int(input())
lst = []
for _ in range(n):
start_time, end_time = map(int, input().split())
lst.append([start_time, end_time])
lst.sort(key=lambda x: (x[1], x[0]))
solution = [lst[0]]
i = 0
for j in range(1, len(lst)):
if lst[j][0] >= lst[i][1]:
solution.append(lst[j])
i = j
print(len(solution))
회의실 배정 문제는 수업시간에 풀어봤던 문제라 쉽게 풀었다.
알고리즘
그리디 알고리즘으로
회의를 끝나는 시간을 기준으로 정렬.
시작하는 시간과 끝나는 시간이 같을 경우도 있기 때문에
x[1]인 끝나는 시간만이 아니라 x[1], x[0]으로 정렬 해주었다.
-> lst.sort(key=lambda x: (x[1], x[0])
그 후 가장 일찍 종료하는 회의를 선택.
다음 회의의 시작 시각이 직전에 선택된 회의의 종료 시각 이전이면 포기, 이후면 선택한다.