1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Did you try sorting plus greedy assignment? Most attractive girl matched with a boy who would invite her, with the highest lower bound etc. $\endgroup$
    – gnasher729
    Commented Nov 6, 2017 at 8:10
  • $\begingroup$ Thanks for the reply. :) So take the most attractive girl. Assign her to the boy who will take her, but has the least wiggle room. Then take next most attractive girl and again assign to the boy who will take her, but has the least wiggle room? And so on? Are you sure this will guarantee there is no other assignment with more pairs on the dance floor? $\endgroup$
    – Edza
    Commented Nov 6, 2017 at 8:17
  • $\begingroup$ In mathematics, when we are not sure of a claim we try to prove or disprove it. $\endgroup$
    – Yuval Filmus
    Commented Nov 6, 2017 at 9:21
  • 1
    $\begingroup$ The "standard" problem is called "marriage problem". $\endgroup$
    – Raphael
    Commented Nov 6, 2017 at 9:28

1 Answer 1

Reset to default
1
$\begingroup$

Algorithm: Pick girl #i where $P_i$ is as high as possible. Eligible boys are those with $A_j ≥ P_i ≥ B_j$. If there is no eligible boy then she is not matched, otherwise match her with eligible boy #j, where $B_j$ is as large as possible. Then match the remaining boys and girls in an optimal way.

If instead you match her with boy #k or with nobody, then you can just swap boy #j and boy #k, and you get a result either as good as promised.

Improve this answer
$\endgroup$
3
  • $\begingroup$ You got A and B wrong. Both in the inequality and the single B should be A. Otherwise I will accept this as the correct answer. Thanks :) $\endgroup$
    – Edza
    Commented Nov 9, 2017 at 14:53
  • $\begingroup$ What do you mean by "If instead you match her with boy #k or with nobody,". How could you swap with "nobody" without breaking everything? $\endgroup$
    – Edza
    Commented Nov 9, 2017 at 15:59
  • $\begingroup$ Thanks for the general idea. Looks correct. Accepted as answer. $\endgroup$
    – Edza
    Commented Nov 10, 2017 at 12:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.