There are n girls and n boys. Each girl i has an objective attractiveness constant Pi (a natural number). The bigger the number, the more attractive. Each boy has a range in which he is comfortable asking the girl out [Ai, Bi] (inclusive). A boy will not ask someone out who is below Ai or above Bi.

I need to pair as many of them as I can for a single dance in O(n*logn) time.

I tried building some kind of a tree in O(n) and then using that three in O(logn) repeatedly against the whole list. I've spent some solid 3 hours on this problem and I'm really not getting anywhere. I've tried to build a dependency tree, I've treed weighted priority queues. I considered some constraint satisfaction algorithms, but as far as I recall they are all nowhere near O(n*logn).

Nothing seems to work. But I do clearly see that this has to be reduced to some other standard computer science problem.

However I've had no luck looking up "load balancing" or "pair assignment". I've no idea what are the right keywords.

This seems the be the kind of problem data centers have when assigning load to virtual machines. Or web requests over the world for large web sites. For example a server can sustain a load in [Ai, Bi] range (let's say RAM in GB's 4-8GB) and our target application needs 5GB. Now let's say we have n of both of these (target applications and servers). How to pair them so as much get paired? Thanks.