到底要不要去AP的实验室做postdoc啊？# Biology - 生物学
s*x
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.)
谁说说怎么做？
多谢！
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.)
谁说说怎么做？
多谢！
