Python에서 작업을 예약하여 최대 이익을 얻는 프로그램

<시간/>

각 간격에 세 개의 값[시작, 끝, 이익]이 포함된 간격 목록이 있다고 가정합니다. 우리는 한 번에 하나의 작업만 수행할 수 있으므로 얻을 수 있는 최대한의 이익을 찾아야 합니다.

따라서 입력이 간격 =[[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]인 경우 출력은 350이 됩니다. 이 두 간격 [1, 2, 100] 및 [2, 100, 250]을 취할 수 있으므로

이 문제를 해결하기 위해 다음 단계를 따릅니다.

d :=값으로 목록을 포함하는 빈 지도
n :=0
각(시작, 끝, 이익)에 대해 간격을 두고 수행합니다.
- 끝> n이면
  - n :=끝
d[end]에 쌍(start, end) 삽입
A :=크기가 n + 1이고 0으로 채워지는 목록
범위 0에서 A 크기까지의 경우
- 끝이 d이면
  - d[end]의 각 (시작, 이익) 쌍에 대해 수행
    - A[end] :=A[end], (A[start] + 이익) 및 A[end - 1]의 최대값
- 그렇지 않으면
  - A[end] :=A[end - 1]
A의 마지막 값을 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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]]