Python으로 작업 스케줄링하여 최대 수익 구하기

각 구간(interval)이 [시작 시간, 종료 시간, 수익]의 세 가지 값을 담고 있는 목록이 있다고 가정해 봅시다. 동시에는 한 번에 하나의 작업만 수행할 수 있으며, 우리는 이 조건에서 얻을 수 있는 최대 수익을 찾아야 합니다.

예를 들어 입력이 intervals = [[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]라면 출력은 350이 됩니다. 서로 겹치지 않는 두 구간 [1, 2, 100]과 [2, 100, 250]을 선택하면 수익 100 + 250 = 350을 얻을 수 있기 때문입니다.

문제 해결 접근 방식

이 문제는 다이나믹 프로그래밍(DP)을 활용해 효율적으로 해결할 수 있습니다. 각 시점까지 얻을 수 있는 최대 수익을 누적해 나가는 방식입니다. 절차는 다음과 같습니다.

• d := 리스트를 값으로 가지는 빈 딕셔너리(defaultdict)를 생성합니다.
• n := 0으로 초기화합니다.
• intervals의 각 (start, end, profit)에 대해:
  • end > n이면 n := end로 갱신합니다.
• d[end]에 (start, profit) 쌍을 삽입합니다.
• A := 크기가 n + 1인 리스트를 만들고 0으로 채웁니다.
• end를 0부터 A의 크기까지 반복합니다:
  • end가 d에 존재하면:
    • d[end]의 각 (start, profit) 쌍에 대해:
      • A[end] := max(A[end], A[start] + profit, A[end - 1])
  • 그렇지 않으면:
    • A[end] := A[end - 1]
• A의 마지막 값을 반환합니다.

Python 구현 예제

다음 구현을 통해 더 잘 이해할 수 있습니다 −

from collections import defaultdict
class Solution:
   def solve(self, intervals):
      d = defaultdict(list)
      n = 0
      for start, end, profit in intervals:
         if end > n:
            n = end
         d[end].append([start, profit])
      A = [0 for i in range(n + 1)]
      for end in range(len(A)):
         if end in d:
            for start, profit in d[end]:
               A[end] = max(A[end], A[start] + profit, A[end - 1])
         else:
            A[end] = A[end - 1]
      return A[-1]
ob = Solution()
intervals = [[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]
print(ob.solve(intervals))

입력

[[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]

출력

350

동작 원리 요약

핵심 아이디어는 배열 A의 각 인덱스(end)를 '해당 시간까지 완료 가능한 작업들로 얻을 수 있는 최대 수익'으로 정의하는 것입니다. 어떤 작업이 end 시점에 끝난다면, 그 작업을 선택했을 때의 수익(A[start] + profit)과 그렇지 않았을 때의 수익(A[end - 1]) 중 더 큰 값을 취하면 됩니다. 이렇게 하면 모든 작업을 순회한 후 A의 마지막 값이 곧 전체 최대 수익이 됩니다.