算法，块叠放 - 图论

Question

算法，块叠放 - 图论

4

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

我们有n个大小为a1×b1,...,an×bn的矩形。我们想要用这些矩形建造一个最高的塔。在一座塔中，如果一个宽度为w的矩形放在另一个宽度为w'的矩形上面，则要求w≤w'。我们可以旋转矩形（例如，一个a×b的矩形可以变成一个b×a的矩形）。请给出一个O(n)的算法，找到可能的最高塔的高度。（例如，如果输入是11×11、8×2、1×10，则解决方案是高度为29的塔=11+8+10。）

- Pat

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Terry Li · Accepted Answer

如果我理解问题正确的话，您总是可以通过将 Math.max(ai,bi) 求和来找到最高可能的塔的高度。由于您不需要建造塔，所以时间复杂度只有 O(n)。否则，您需要使用 O(nlogn) 的时间复杂度（按矩形高度排序）。