tag:blogger.com,1999:blog-6314876008291942531.post4918621913356099885..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Overlapping rectanglesUnknownnoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6314876008291942531.post-16136694020257280752009-02-17T04:53:00.000-08:002009-02-17T04:53:00.000-08:00I like this problem since it is a classical exampl...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)codingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.com