I like this problem since it is a classical example of simple computational geometry. A solution is like the following. Sort the x-coordinates of the rectangles in time O(nlogn), and maintains the y-coordinates in a binary search tree (BST). If the current x-coordinate is on the left side of the rectangle, then insert in the BST the corresponding y-coordinates. If the current x-coordinate is on the right side of the rectangle, then remove the corresponding y-coordinates from the BST. Before inserting, search the BST to find an overlap with current y-coordinate. There are 2n search and each one takes O(logn). The total complexity is O(nlogn)
I like this problem since it is a classical example of simple computational geometry. A solution is like the following. Sort the x-coordinates of the rectangles in time O(nlogn), and maintains the y-coordinates in a binary search tree (BST). If the current x-coordinate is on the left side of the rectangle, then insert in the BST the corresponding y-coordinates. If the current x-coordinate is on the right side of the rectangle, then remove the corresponding y-coordinates from the BST. Before inserting, search the BST to find an overlap with current y-coordinate. There are 2n search and each one takes O(logn). The total complexity is O(nlogn)
ReplyDelete