파이썬에서 가장 긴 체인을 형성하는 상자의 수를 찾는 프로그램은 무엇입니까?

<시간/>

상자 목록이 있다고 가정하고 여기 각 항목에는 두 개의 값 [start, end](start

따라서 입력이 블록 =[ [4, 5], [5, 6], [4, 8], [1, 2], [2, 4] ]인 경우 출력은 4가 됩니다. 체인을 형성할 수 있습니다:[1, 2], [2, 4], [4, 5], [5, 6]

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

상자가 비어 있으면
- 0 반환
목록 상자 정렬
dic :=빈 지도
상자의 시작 s와 끝 e에 대해 다음을 수행하십시오.
- dic[e] :=dic[e] 및 dic[s] + 1의 최대값
dic
의 모든 값 목록의 최대값을 반환합니다.

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

import collections

class Solution:
   def solve(self, boxes):
      if not boxes:
         return 0
      boxes.sort()
      dic = collections.defaultdict(int)
      for s, e in boxes:
         dic[e] = max(dic[e], dic[s] + 1)
      return max(dic.values())

ob = Solution()
boxes = [
   [4, 5],
   [5, 6],
   [4, 8],
   [1, 2],
   [2, 4]
]
print(ob.solve(boxes))

입력

[[4, 5],
[5, 6],
[4, 8],
[1, 2],
[2, 4] ]