# Optimizing Pairings Between Integers and Intervals for Maximal Matching

Consider the scenario where we are given a collection of n integers. These integers are unordered and may include duplicates. Additionally, we have a set of m ranges, each defined by two integers representing the lower and upper boundaries of the interval. Similar to the integers, these intervals are unordered and duplicates are allowed.

The objective is to create pairs between the integers and the intervals under the following conditions:

An integer can only be matched with an interval if it falls within the range of the interval. For instance, the number 4 can be paired with the interval [3, 10], but not with [5, 10]. Each integer is allowed to pair with only one interval, and vice versa. The goal is to maximize the total number of such pairs. We are solely interested in determining the maximum number of possible pairs, rather than identifying the specific pairings.

For illustration:

Given a single number 2 and an interval [4, 10], there would be no possible pairing, resulting in an output of 0. With the number 2 and an interval [2, 10], a single pair can be formed, leading to an output of 1. For numbers 3, 7, 8, 12 and intervals [0, 10], [5, 15], [20, 25], the maximum number of pairs that can be formed is 2. While a straightforward approach might involve an algorithm with time complexity of O(nm), the challenge lies in devising a more efficient solution. The question is whether it's feasible to construct an algorithm with a time complexity of O(max(nlog(n), mlog(m), nlog(m), m*log(n))), thereby optimizing the process of determining the maximal number of pairs

Consider the case of maximal bipartite matching between the two parties: the set of integers (let's call it $$Z$$) and the set of intervals (let's call it $$I$$). From Kőnig's theorem, we know that the maximum possible matching size can be at most $$\min(|Z|, |I|)$$. Now, how do I efficiently find a maximal matching?
One can use an interval tree $$T$$ to store all the intervals in $$I$$. The construction takes $$O(|I|\log|I|)$$ time with $$O(|I|)$$ storage cost. Now for each integer $$z\in Z$$, we query in $$T$$ to see if it hits some interval $$i\in I$$. We pair $$(z, i)$$ and delete $$i$$ from $$T$$. Searching and deletion both take $$O(\log|I|)$$ time. Thus, we have an $$O((|I|+|Z|)\log|I|)$$ algorithm for maximal matching.
For a maximum matching one can use the Hopcroft–Karp–Karzanov algorithm to get an $$O(m\sqrt{n})$$ algorithm where the graph has $$n$$ vertices and $$m$$ edges. Here we have $$n = |I|+|Z|$$ and $$m \le |I||Z|$$. Since $$m$$ can be of order $$O(n^2)$$ this gives you a $$O(n^{2.5})$$ algorithm for dense graphs. To construct this graph, you need $$O(n+m)$$ operations. In case of sparse graph, the maximum matching can be obtained in $$O(m\log{n})$$ time (see this ref). In case of sparse input, we can employ interval searching to construct the graph efficiently.