[google面试题]Describe an algorithm that takes an unsorted array of axis‐aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair.
Axis‐aligned means that all the rectangle sides are either parallel or perpendicular to the x‐andy‐axis.You can assume that each rectangle object has two variables in it:the x‐y coordinates of the upper‐left corner and the bottom‐right corner.Good Answer:Create a sorted array of the x coordinates of the left and right edges of the rectangles.Then,use a "scanline" to move from left to right through the rectangles.Keep a binary search tree containing they coordinates of the top and bottom edges of the rectangles that over lap the scanline.For each element of the array,check whether it is a left or right edge.If it is a right edge,remove the corresponding top and bottom edges from the BST.If it is a left edge,search the BST for rectangles that over lap the current rectangle;if there is one,return the overlap.Then,add they coordinates of the top and bottom edges of the rectangle to the BST.The search takes O(nlogn) time,since it takes O(nlogn) time to sort the rectangles and each of the 2nd iterations takes O(logn) time.
页:
[1]