상자 목록이 있다고 가정하고 여기 각 항목에는 두 개의 값 [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] ]
출력
4