Is there an efficient algorithm for the following problem?
Input: Set of holes and pegs. Each hole/peg is an interval $[\ell,u]$ with integer endpoints.
Question: Can all the holes be filled using the pegs given, satisfying the following conditions?
- Each peg is assigned to at most one hole.
- No hole is assigned more than one peg.
- If peg $p$ is assigned to hole $h$, then the interval $p$ must be contained in the interval $h$.
Here's a picture to help clarify:
My algorithm: For each hole, check if any peg can be assigned to this hole.
Issues: Unfortunately, this doesn't work. See Scenario 3 in the picture above: my algorithm assigns the same peg ($[1,2]$) to multiple holes ($[1,2]$ and $[1,3]$), which is not legal.
My second attempt: I tried to construct an algorithm that marks a peg as unavailable it is used.
- Let available_pegs = all input pegs
- For each hole, check if any peg from available_pegs can be assigned to this hole.
- If a peg is found, remove it from available_pegs and assign it to that hole.
Issues: Unfortunately, this doesn't work either. It can fail in Scenario 2: if I assigned peg $[1,2]$ to hole $[1,3]$, peg $[1,2]$ will be marked unavailable and now there is now way to fill the hole $[1,2]$. Thus in this example the algorithm would say that there are not enough pegs to assign to all the holes, which is wrong.