pairing numbers and intervals

Question

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?

Answer 1

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.