Hi There.

I am a software developer and now working on some project related to documents generation and viewing. There at some point I have a function that needs to find rectangles that do not contains some other rectangles. We implemented it in O(n^2), but I feel it is possible to do much faster. Here is the problem:

I have an array of rectangles. These rectangles can intersect and overlap. Some are inside each other. Need to write an function, that will return an array of rectangles, that do not contain other rectangles (partial intersect do not count). Exactly same rectangles also count.

I am not sure is it possible to do faster, or is there any algorithm for it. Maybe some kind of sweepline or convex hull, but that's just a guess. That's why t decided to ask the Codeforces community. Looking forward to your ideas. I hope it is a right place for such things.