# How do solve assignment of one interval to another?

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.

• Since your question specifically asks where do I learn about interval related problems, here might be a good start: en.wikipedia.org/wiki/Interval_schedulinghttps://… Jul 27 '17 at 11:13
• There's a whole body of work on assignment problems, you may want to peruse the literature.
– Raphael
Jul 27 '17 at 16:30
• Here is a recursive python program that solves this problem: repl.it/JlXf/1 Jul 27 '17 at 18:46

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".