Monday, July 6, 2015

ITInt5: maximum boxes

July 6, 2015
Problem statement:
Link: http://www.itint5.com/oj/#34
问题:
n块积木,每块积木有体积vol和重量weight两个属性,用二元组(vol, weight)表示。
积木需要搭成竖直的塔状,上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。
样例:
7个积木boxes:
[(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110), (80, 12)]
最多可以搭6个积木,从上到下分别为:
(56, 90), (60, 95), (65, 100), (68, 110), (70, 150), (75, 190)
所以函数应该返回6
题目来源:CRACKING THE CODING INTERVIEW 9.7
Solution: 先按照vol进行排序,题目就变成了根据weight寻找最长严格递增子序列。
Share C# practice:

No comments:

Post a Comment