Giả sử chúng ta có một danh sách các hộp, ở đây mỗi mục nhập có hai giá trị [bắt đầu, kết thúc] (bắt đầu
Vì vậy, nếu đầu vào giống như các khối =[[4, 5], [5, 6], [4, 8], [1, 2], [2, 4]], thì đầu ra sẽ là 4, như chúng ta có thể tạo thành chuỗi:[1, 2], [2, 4], [4, 5], [5, 6]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
nếu các hộp trống, thì
trả về 0
sắp xếp các hộp danh sách
dic:=một bản đồ trống
đối với mỗi chữ cái bắt đầu và chữ cái kết thúc trong các hộp, hãy thực hiện
dic [e]:=tối đa dic [e] và dic [s] + 1
trả về giá trị tối đa trong danh sách tất cả các giá trị của dic
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
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))
Đầu vào
[[4, 5],
[5, 6],
[4, 8],
[1, 2],
[2, 4] ]
Đầu ra
4
