大家来讨论一下这个求长方形面积的问题吧 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

大家来讨论一下这个求长方形面积的问题吧

大家来讨论一下这个求长方形面积的问题吧# JobHunting - 待字闺中

b*n2013-03-19 07:03

1 楼

Given a group of rectangles whose edges are parallel to X-axis or Y-axis,
find the total area they cover.
想到line sweep的办法，不过好像时间复杂度是n^2, 想不出nlogn的办法。搜了一下，
发现这个：
http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangle
也是O(n^2)时间的。

r*h2013-03-19 07:03

2 楼

O(n log n)的方法需要使用线段树
我觉得面试能用O(n^2)就不错了

b*n2013-03-19 07:03

3 楼

我的理解是，线段树只能保证新的长方形开始或者结束的时候logn的时间更新，但是计
算每一段x包含的面积的时候，最坏情况下不还是需要O(n)吗？

x*y2013-03-19 07:03

4 楼

For example, you can build a segment tree for y and move along x to insert
into and take away from the segment tree of correpsonding range Y. Remember
the x value of last update, and on current update, use the difference of x
* range Y covered by segment tree.

【在 b*****n 的大作中提到】