在Python中找到形成最长链的方框数目的程序？

假设我们有一个盒子列表，每个条目都有两个值[start，end]（start＜end）。如果一个盒子的末端等于另一个盒子的开头，我们可以将两个盒子拼接在一起。我们必须找到最长的盒子链长度。

因此，如果输入是blocks =[ [4, 5]，[5, 6]，[4, 8]，[1, 2]，[2, 4] ]，那么输出将为4，因为我们可以形成链：[1，2]，[2，4]，[4，5]，[5，6]

要解决此问题，我们将遵循以下步骤：

• 如果盒子为空，则
  • 返回0
• 将列表boxes排序

• dic：=空映射

• 对于盒子中的每个start s和end 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