4
$\begingroup$

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:

examples of pegs and holes

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.

$\endgroup$
3
  • $\begingroup$ 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://… $\endgroup$ Jul 27 '17 at 11:13
  • $\begingroup$ There's a whole body of work on assignment problems, you may want to peruse the literature. $\endgroup$
    – Raphael
    Jul 27 '17 at 16:30
  • $\begingroup$ Here is a recursive python program that solves this problem: repl.it/JlXf/1 $\endgroup$
    – miracle173
    Jul 27 '17 at 18:46
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Now I understood what "operations research" is!! Exactly what I was looking for. $\endgroup$
    – user75291
    Jul 27 '17 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy