Pythonで最長のチェーンを形成するボックスの数を見つけるプログラム？

ボックスのリストがあるとします。ここでは、各エントリに2つの値[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