算法， block 堆叠 - 图论

Question

我正在为我的算法课努力解决这个问题。它在图论部分。我想我应该使用最大加权匹配。但不确定如何构建二分图。有什么建议吗？

我们有 n 个大小为 a1 × b1 的矩形，... . . , 一个 × bn。我们想用矩形 build 最高的塔。在塔中，如果宽度为 w 的矩形位于宽度为 w 的矩形之上w'那么我们要求 w ≤ w'.我们可以旋转矩形(即，a × b 矩形可以变成b × 一个矩形)。给出一个复杂度为 O(n) 的算法，找出尽可能高的塔的高度。(例如，如果输入为 11 × 11、8 × 2、1 × 10，则解为高度为 29 = 11 + 8 + 10 的塔。)

Answer 1

如果我对问题的理解正确，你总能通过求和 Math.max(ai,bi) 找到可能的最高塔的高度。因为你不需要 build 塔，所以它只是O(n)。否则你需要 O(nlogn)(按矩形的高度排序)。