s**x
发帖数: 7506 | 1 14.3-4
given an interval tree T and interval i, describe how all intervals in T
that overlap i can be listed in O(min(n, klogn)) time, where k is the number
of intervals in the output list. (optional: find a solution that does not
modify the tree)
14.3-7
VLSI databases commonly represent an intergrated circuit as a list of
rectangles, assume that each rectangle is rectilinearly oriented(side
parallel to the x- and y-axis), so that a representation of a rectangle
consists of its minimum and maximum x, y coordinates. given an O(nlogn)-time
algorithm to decide where or not a set of rectangles so represented
contains two rectangles that overlap. your algorithm need not report all
intersecting pairs, but it must report that an overlap exist if one
rectangle entirely covers another, even if the boudary lines do not
intersect. (Hint: move a "sweep" line accross the set of rectangles.)
谁说说怎么做？
多谢！ | f**********t
发帖数: 1001 | 2 关注一下。
google的Interval问题考察的是不是这个？
如：
Assume we have n people. Each one has a starting time and ending
time. For any people, set flag to true if his/her time range overlaps
with anyone else's. | s**x
发帖数: 7506 | 3 not really. for this one, there is a better way.
discussed before and also on the web. the idea is split each pair and then
sort all the numbers and the walk through the list.
thinking about lost of "()", if will be nested if there is a overlap. O(
nlogn).
【在 f**********t 的大作中提到】
: 关注一下。
: google的Interval问题考察的是不是这个？
: 如：
: Assume we have n people. Each one has a starting time and ending
: time. For any people, set flag to true if his/her time range overlaps
: with anyone else's.
| F**r
发帖数: 84 | 4 14.3-4 is straightforward, directly utilize the properties of interval tree.
14.3-7 straightforward too, apply interval tree in 2-D respectively.
number
time
【在 s**x 的大作中提到】
: 14.3-4
: given an interval tree T and interval i, describe how all intervals in T
: that overlap i can be listed in O(min(n, klogn)) time, where k is the number
: of intervals in the output list. (optional: find a solution that does not
: modify the tree)
: 14.3-7
: VLSI databases commonly represent an intergrated circuit as a list of
: rectangles, assume that each rectangle is rectilinearly oriented(side
: parallel to the x- and y-axis), so that a representation of a rectangle
: consists of its minimum and maximum x, y coordinates. given an O(nlogn)-time
| d*******d
发帖数: 2050 | 5 2,先把所有的x坐标拿出来排个序,然后在y坐标上建interval tree,scanline从左往右,
每次touch rectangle left的时候,放入y1-y2到tree,同时看有没有重叠,touch到
rectangle右边的时候,拿掉.
tree.
【在 F**r 的大作中提到】
: 14.3-4 is straightforward, directly utilize the properties of interval tree.
: 14.3-7 straightforward too, apply interval tree in 2-D respectively.
:
: number
: time
| s**x
发帖数: 7506 | 6 14.3-4, any details?
tree.
【在 F**r 的大作中提到】
: 14.3-4 is straightforward, directly utilize the properties of interval tree.
: 14.3-7 straightforward too, apply interval tree in 2-D respectively.
:
: number
: time
|
|
