1
$\begingroup$

subject: pairing numbers and intervals

Let NUMBERS be a list of n integer numbers. The numbers are listed in no specific order. Duplicates are possible.

Let INTERVALS be a list of m intervals. The low and high limits of the intervals are integer numbers. The intervals are listed in no specific order. Duplicates are possible.

We want to pair the numbers and intervals as thus:

  • A number can only be paired with an interval to which it belongs. For example, 4 and [3, 10] can be paired, 4 and [5, 10] cannot.
  • A number cannot be paired with more than one interval.
  • An interval cannot be paired with more than one number.
  • The number of pairs is maximal.
  • We are not interested in the pairs themselves, only in the (maximal) number of pairs.

To summarize:

  • input = NUMBERS, INTERVALS
  • output = maximal number of pairs

Example 1:

  • NUMBERS = 2
  • INTERVALS = [4, 10]
  • output = 0

Example 2:

  • NUMBERS = 2
  • INTERVALS = [2, 10]
  • output = 1

Example 3:

  • NUMBERS = 3, 7, 8, 12
  • INTERVALS = [0, 10], [5, 15], [20, 25]
  • output = 2

It is relatively simple to devise an O(n*m) algorithm to solve this problem. I seriously doubt that there exist any O(n) + O(m) algorithm, but what about an O(max(n*log(n), m*log(m), n*log(m), m*log(n))) algorithm?

$\endgroup$
2
  • $\begingroup$ Can you argue the validity of ordering NUMBERS ascendantly as well as INTERVALS by low and high limit, and greedily looking for "the lowest" interval containing the first number, alternating with looking for the lowest number contained in the first interval? $\endgroup$
    – greybeard
    Feb 9, 2023 at 17:35
  • 1
    $\begingroup$ @greybeard if I understand your idea and intervals can overlap then that greedy heuristic will fail if $N=\{4,5\} $ and $I=\{[1,5],[2,4]\}$. $\endgroup$
    – Russel
    Feb 10, 2023 at 1:12

1 Answer 1

0
$\begingroup$

Your problem is equivalent to the problem of finding a maximum matching in a convex bipartite graph (a bipartite graph $G=(A,B,E)$ where the vertices on one side, say $A$, admit an ordering $a_1,\ldots,a_n$ such that each vertex in $B$ is adjacent to an interval $a_i,\ldots,a_j$ for some $1\leq i\leq j\leq n$). Googling "maximum matching convex graphs" I found this paper: A Linear Time Algorithm for Maximum Matchings in Convex, Bipartite Graphs (by G. Steiner and J. S. Yeomans) that claims the problem is actually solvable in time proportional to $|B|$! So, in your case, the problem is solvable in time $O(m)$.

EDIT: Both this paper and others require you to represent the neighborhood of each vertex $b$ in $B$ by the first and last (in the implied ordering) vertex in $A$ that is adjacent to $b$. This requires you to sort the integers (in $O(n \log n)$ time) and replacing each interval with the indices of the first and last integer that is contained in the interval (in $O(m \log n)$ time). Thus we reach your guessed time-bound (unless, of course, there is some clever way to accomplish this without sorting). My bad for not spotting this right away.

$\endgroup$
2
  • $\begingroup$ That looks more difficult than I was hoping for, but thanks a lot for posting this! $\endgroup$ Feb 10, 2023 at 14:50
  • $\begingroup$ There probably are simpler algorithms that still are quite fast; i'd advise you to just browse Google Scholar. $\endgroup$
    – Highheath
    Feb 10, 2023 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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