สมมติว่าเรามีรายการกล่อง ที่นี่แต่ละรายการมีสองค่า [start, end] (start
ดังนั้นหากอินพุตเป็นเหมือนบล็อก =[ [4, 5], [5, 6], [4, 8], [1, 2], [2, 4] ] ผลลัพธ์จะเป็น 4 ตามที่เรา สามารถสร้างห่วงโซ่ได้:[1, 2], [2, 4], [4, 5], [5, 6]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
ถ้ากล่องว่างก็
คืนค่า 0
เรียงลำดับกล่องรายการ
dic :=แผนที่ว่างเปล่า
สำหรับแต่ละการเริ่มต้นและสิ้นสุด 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
