How do solve assignment of one interval to another?

Question

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?

1. Each peg is assigned to at most one hole.
2. No hole is assigned more than one peg.
3. 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.

1. Let available_pegs = all input pegs
2. For each hole, check if any peg from available_pegs can be assigned to this hole.
3. 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.

Answer 1

This is an instance of bipartite matching (i.e., the assignment problem with no costs). It can be solved by standard methods, such as network flow algorithms (e.g., Ford-Fulkerson), the Hopcroft-Karp algorithm, or using linear programming. See also https://cs.stackexchange.com/a/61264/755.

In particular, you can build a bipartite graph, with one "left vertex" per peg, and one "right vertex" per hole, and an edge from peg $p$ to hole $h$ if the interval $p$ is contained in the interval $h$. Compute the maximum cardinality matching for this bipartite graph. If this matching covers every hole, then the answer to your problem is "yes", otherwise the answer is "no".