用 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

• 对列表框进行排序

• 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

相关文章

• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?
• 用 Python 编写程序检查我们是否可以从给定的字符串字符中创建 k 个回文?
• 如何使用 Python 和 openpyxl 在 excel 中创建图表?
• 用 Python 编写程序来找出斐波那契数列中最小的和为 n 的数?
• 用 Python 执行 excel 电子表格操作的程序?
• 如何在 Python 中将数据值插入字符串?
• 用 Python 编写程序来计算将所有值转换为相同值所需的操作次数?
• 用 Python 编写程序检查是否可以将两个分区分成总和相等的组?
• 如何在 Python 中添加命令行参数?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/