b*****n
发帖数: 143 | 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**h
发帖数: 1288 | 2 O(n log n)的方法需要使用线段树
我觉得面试能用O(n^2)就不错了 |
b*****n
发帖数: 143 | 3 我的理解是，线段树只能保证新的长方形开始或者结束的时候logn的时间更新，但是计
算每一段x包含的面积的时候，最坏情况下不还是需要O(n)吗？ |
x***y
发帖数: 633 | 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 的大作中提到】
: 我的理解是，线段树只能保证新的长方形开始或者结束的时候logn的时间更新，但是计
: 算每一段x包含的面积的时候，最坏情况下不还是需要O(n)吗？
|
n**m
发帖数: 122 | |
N*D
发帖数: 3641 | |
s*********s
发帖数: 318 | |
s*********s
发帖数: 318 | 8 Google了一下。还有求这些长方形构成的轮廓线的。 |
r**h
发帖数: 1288 | 9 是啊，都属于线段树的典型应用
根据我搞ACM的同学说，这些属于ACM的水题。。。T T
【在 s*********s 的大作中提到】
: Google了一下。还有求这些长方形构成的轮廓线的。
|
h**6
发帖数: 4160 | |
