[itint5] 刷题记录板 - 美国米群网 － 海外华人留学生最大面试求职社交平台 － 计算机 商科 面试 面经 内推 刷题 算法 职场 绿卡 家庭 休闲 - Powered by Discuz!
有一个H * W的屏幕，左上角坐标为(0,0)，右下角坐标为(H,W)。屏幕中已有n个与坐标轴平行的矩形窗口，存放在数组rects中，第i个矩形窗口的左上坐标为(rects【i】.x1, rects【i】.y1)，右下坐标为(rects【i】.x2, rects【i】.y2)。现需要放置一个h * w的新矩形窗口，使得新窗口与已有的窗口重叠的总面积最小。请计算最小的重叠总面积。已知条件：
• 已有的窗口都完全在屏幕中。
• 摆放的新窗口也要完全在屏幕中。
• 已有的窗口互相不重叠。
• W, H<=10000，n<=100。
Solution: 贪心算法.
为使矩形覆盖最小:
所求矩形的上边要么贴着边界，要么贴着某个已有矩形的下边
所求矩形的下边要么贴着边界，要么贴着某个已有矩形的上边
所求矩形的左边要么贴着边界，要么贴着某个已有矩形的右边
所求矩形的右边要么贴着边界，要么贴着某个已有矩形的左边
总可以找到一个满足最小覆盖条件的矩形，这个矩形的边要么与大窗口的边缘重合，要么和已知矩形的边重合。 这样，只需要枚举O(n^2)的左上点坐标，总的时间复杂度O(n^3).
Read full article from [itint5] 刷题记录板 - 美国米群网 － 海外华人留学生最大面试求职社交平台 － 计算机 商科 面试 面经 内推 刷题 算法 职场 绿卡 家庭 休闲 - Powered by Discuz!
No comments:
Post a Comment