🥈 19621번: 회의실 배정 2

👉🏻 19621번: 회의실 배정 2

 

import sys; input=sys.stdin.readline

n = int(input())
info = [[0] * 3 for _ in range(n)]
parts = [0] * n

for _ in range(n):
    start, end, part = map(int, input().split())
    info[_][0] = start
    info[_][1] = end
    info[_][2] = part

info.sort()

for i in range(n):
    start_time = info[i][0]
    parts[i] = info[i][2]
    for j in range(i):
        if info[j][1] <= start_time:
            parts[i] = max(parts[i], parts[j] + info[i][2])

print(max(parts))

• 그리디 + DP를 이용하여 최대 회의 인원을 갱신하였습니다.
• 회의들을 시작 시간 순으로 정렬함으로써, 각 회의마다 이전 회의들끼리 겹치는지를 조사하였습니다.
• 문제에서는 회의 수가 최대 25개이기에 이중 for문을 사용했지만, 회의 수가 늘어남에 따라 bisect 모듈로 시간 복잡도를 줄여볼 수 있겠습니다.