偶出一题，不知道有没有人会# JobHunting - 待字闺中
w*s
1 楼
给出若干矩形，矩形可以从大到小重叠摆放，但是放在上面的矩形必须能够完全放入下
面的矩形中，每个矩形上至多只能放另外一个矩形，摆放的时候矩形的边必须相互垂直
或平行（不可任意旋转），求最优摆放方案使得总占地面积最小。
面试应该不会考这么偏的。
面的矩形中，每个矩形上至多只能放另外一个矩形，摆放的时候矩形的边必须相互垂直
或平行（不可任意旋转），求最优摆放方案使得总占地面积最小。
面试应该不会考这么偏的。
z*n
2 楼
这个不就是求最少的路径覆盖所有点，然后转化成二分图匹配
w*s
3 楼
是占地面积，类似于最少路径，但是有点不一样
【在 z***n 的大作中提到】
: 这个不就是求最少的路径覆盖所有点，然后转化成二分图匹配
【在 z***n 的大作中提到】
: 这个不就是求最少的路径覆盖所有点，然后转化成二分图匹配
l*u
4 楼
先sort矩形长度，由大到小。然后以第一的宽，找下个小的宽的矩形，这是一对。一对
一对找下去。凑不成对的单放。
【在 w*******s 的大作中提到】
: 给出若干矩形，矩形可以从大到小重叠摆放，但是放在上面的矩形必须能够完全放入下
: 面的矩形中，每个矩形上至多只能放另外一个矩形，摆放的时候矩形的边必须相互垂直
: 或平行（不可任意旋转），求最优摆放方案使得总占地面积最小。
: 面试应该不会考这么偏的。
一对找下去。凑不成对的单放。
【在 w*******s 的大作中提到】
: 给出若干矩形，矩形可以从大到小重叠摆放，但是放在上面的矩形必须能够完全放入下
: 面的矩形中，每个矩形上至多只能放另外一个矩形，摆放的时候矩形的边必须相互垂直
: 或平行（不可任意旋转），求最优摆放方案使得总占地面积最小。
: 面试应该不会考这么偏的。
z*s
5 楼
楼上什么二分匹配，贪心，完全是扯淡，自己都没仔细想想还好意思发。
想了几个特殊情况，发现这个题还真有点意思，转成DAG之后有点卡住了，感觉要暴力
或者dp了，lz说说数据规模吧。
矩形的长宽范围还有矩形个数的范围都是多少，时限多少？
想了几个特殊情况，发现这个题还真有点意思，转成DAG之后有点卡住了，感觉要暴力
或者dp了，lz说说数据规模吧。
矩形的长宽范围还有矩形个数的范围都是多少，时限多少？
w*s
6 楼
类似最少路径覆盖,确实是二分匹配和贪心，但是第二个回复是扯淡，是O(n^2)的时间复
杂度和O(n)的空间复杂度
【在 z****s 的大作中提到】
: 楼上什么二分匹配，贪心，完全是扯淡，自己都没仔细想想还好意思发。
: 想了几个特殊情况，发现这个题还真有点意思，转成DAG之后有点卡住了，感觉要暴力
: 或者dp了，lz说说数据规模吧。
: 矩形的长宽范围还有矩形个数的范围都是多少，时限多少？
杂度和O(n)的空间复杂度
【在 z****s 的大作中提到】
: 楼上什么二分匹配，贪心，完全是扯淡，自己都没仔细想想还好意思发。
: 想了几个特殊情况，发现这个题还真有点意思，转成DAG之后有点卡住了，感觉要暴力
: 或者dp了，lz说说数据规模吧。
: 矩形的长宽范围还有矩形个数的范围都是多少，时限多少？
h*n
7 楼
经典dp问题。boxstacking简化
http://www.geeksforgeeks.org/dynamic-programming-set-21-box-sta
http://www.geeksforgeeks.org/dynamic-programming-set-21-box-sta
w*s
8 楼
不一样的题
【在 h*****n 的大作中提到】
: 经典dp问题。boxstacking简化
: http://www.geeksforgeeks.org/dynamic-programming-set-21-box-sta
【在 h*****n 的大作中提到】
: 经典dp问题。boxstacking简化
: http://www.geeksforgeeks.org/dynamic-programming-set-21-box-sta
b*e
9 楼
拓扑排序后产生DAG，然后就是按层数一层一层的进行最大二分匹配。二楼说的是正解
。在自己搞清楚自己是否扯着蛋之前不要随便说别人扯蛋。
【在 z****s 的大作中提到】
: 楼上什么二分匹配，贪心，完全是扯淡，自己都没仔细想想还好意思发。
: 想了几个特殊情况，发现这个题还真有点意思，转成DAG之后有点卡住了，感觉要暴力
: 或者dp了，lz说说数据规模吧。
: 矩形的长宽范围还有矩形个数的范围都是多少，时限多少？
。在自己搞清楚自己是否扯着蛋之前不要随便说别人扯蛋。
【在 z****s 的大作中提到】
: 楼上什么二分匹配，贪心，完全是扯淡，自己都没仔细想想还好意思发。
: 想了几个特殊情况，发现这个题还真有点意思，转成DAG之后有点卡住了，感觉要暴力
: 或者dp了，lz说说数据规模吧。
: 矩形的长宽范围还有矩形个数的范围都是多少，时限多少？
相关阅读
贡献一个 一个L家的店面题目offer选择求建议！再来问道面经题Mac上用什么Xml editorFLG 牛人报个推特的卧佛你们公司给你们付手机月费收到据信后遇到这样的情况有人帮忙Saleforce内推吗？哎， 一个中部普通学校毕业的，求问：有什么多线程的复习资料不？问一道面试题大家应该对比自己年纪大的马工多放水google kirkland/seattle team match 求收留Beepi是怎么盈利的？其实很多面试嘛，并不要求你回答得绝对正确当刷题成为一种习惯array 转换成 linkedlist, 在线等, 挺急的--help is still nee基因测序公司研发组的应用专家职位咋样Hulu onsite选西雅图还是洛杉矶？