I was trying to solve 2024 Argentinian Programming Tournament (TAP) problem H (https://mirror.codeforces.com/gym/105321) and got stuck on a subproblem, but the contest doesn't have an editorial.

I have N axis-aligned rectangles that don't intersect each other (not even at corners), but some can be nested inside others. I need to efficiently find the "parent" of each rectangle, meaning the smallest rectangle that completely contains it. The trivial approach would be O(N^2): for each rectangle, check all others to see which contain it, but this would be too slow. I was thinking about sweep line algorithms but I can't figure it out.

Is there a standard algorithm for this problem?

I have a list of pairs of strings (or pairs of hashes) called V. I want to create a list W by removing elements from V such that W has as many pairs as possible and: There are no i,j such that W[i].first==W[j].first There are no i,j such that W[i].second==W[j].second I know it can be solved with max-flow, but the complexity would be at least O(|V|^2) because that would be the amount of edges in the graph. Is there any algorithm faster than that?, the algorithm might be probabilistic.