3
$\begingroup$

Say I have two sets of intervals sorted by time $I_1=[(x_1, y_1),... (x_n, y_n)]$ and $I_2 = [(a_1, b_1)... (a_m, b_m)]$. where $x, y, a, b$ are times in seconds. None of the intervals within $I_1$ intersect, i.e. $x_1 < y_1 < x_2 < y_2 < x_3....$ and same holds for $I_2$ $a_1 < b_1 < a_2 < b_2 < a_3....$

There is however overlap between elements of $I_1$ and $I_2$ so for example $(x_k, y_k)$ can intersect with $(a_j, b_j)$ for some $k\in [1, n], j\in [1,m]$.

Any $(x_k, y_k) \in I_1$ could overlap with multiple intervals of $I_2$ and vice versa. We want to solve two problems

  1. Find a bijective mapping M(or a matching interms of graph theory) from $I_1 -> I_2$ without taking into account the length of the overlap
  2. Find a bijective mapping M which maximizes the length of the overlap(maximal weight matching in graph theory).

Problem 1 is an easy, given the sorted intervals. Like even with a bruteforce geeedy could do a O(n+m) here; For each $(x_1, y_1)$ select the first $(a_i, b_i)$ that intersects and add it to a mapping M, then for $(x_2, y_2)$ start from $(a_{i+1}, b_{i+1})$ and repeat.

Problem 2 is not so trivial since we can have multiple candidates. For example the above algorithm that works for problem 1 fails to find an optimal solution for problem 2 $I_1 = [(1, 5), (6, 12)]$ $I_2=[(1, 2), (3, 7), (8, 12)]$ . One obvious solution is maximum bipartite matching, but maybe there is something else clever we can do to exploit the problem structure?

$\endgroup$
1
  • $\begingroup$ For bijective mapping, do we need $n=m$? For problem 1, can we just map $(x_i, y_i)$ to $(a_i, b_i)$ for all $i$? Or is the goal to find a mapping with the maximum number of overlapping pairs? $\endgroup$
    – John L.
    Commented Oct 16, 2021 at 4:39

1 Answer 1

2
$\begingroup$

Yes, for problem 2, there is a more direct approach.

There is either none or one more overlapping pair of intervals when we add next interval in order of their left endpoints. That fact is the base for the following algorithm using dynamic programming.

  1. Sort all intervals (in either $I_1$ or $I_2$) in order of their left endpoints, breaking ties by their right endpoints.

    • Let variable rightmost_interval keep track of the interval inspected so far with the rightmost right endpoint. If there are two such intervals, choose the one that was inspected earlier.
    • Let variable max_mapped and max_not_mapped keep track of the max length of overlap for all possible partial mappings of intervals inspected so for, with rightmost_interval mapped to an overlapping interval or not mapped to another interval, respectively.
      Here "partial" means some of inspected intervals in $I_1$ may not be mapped to any interval in $I_2$. Only overlaps between corresponding (i.e., as defined by the partial mapping) intervals are considered.

    Initially, rightmost_interval is the first interval while both max_mapped and max_not_mapped are 0.

  2. Inspect the interval one by one, starting from the second one. For each interval inspected, update all variables according to the specification, as shown inside the for loop in the code below.

  3. Return max(max_mapped, max_not_mapped)

    // Given non-overlapping intervals I1 and non-overlapping intervals
    // I2, we can select some intervals in I1 to pair each of them to a
    // different intervals in I2. This method returns the maximum sum of
    // lengths of overlaps between paired intervals.
    long max_overlap(int[][] I1, int[][] I2) {
        if (I1.length == 0 || I2.length == 0) {
            return 0;
        }

        // Combine `I1` and `I2` into one list, `I`.
        int[][] I = new int[I1.length + I2.length][2];
        System.arraycopy(I1, 0, I, 0, I1.length);
        System.arraycopy(I2, 0, I, I1.length, I2.length);

        // Sort `I` by the left endpoints, breaking ties by the right endpoints
        Arrays.sort(I, (i1, i2) -> {
            if (i1[0] != i2[0]) return i1[0] - i2[0];
            else return i1[1] - i2[1];
        });

        // the interval inspected so far with the rightmost right endpoint.
        int[] rightmost_interval = I[0];
        // max total overlap with `rightmost_interval` not mapped to an interval.
        long max_not_mapped = 0;
        // max total overlap with `rightmost_interval` mapped to an overlapping interval.
        // If there is no interval that overlaps `rightmost_interval`, `max_mapped` will be 0.
        long max_mapped = 0;

        for (int i = 1; i < I.length; ++i) {
            int[] current = I[i];
            if (rightmost_interval[1] >= current[1]) {
                max_mapped = Math.max(max_mapped, max_not_mapped + current[1] - current[0]);
                // `rightmost_interval` and `max_not_mapped` stay the same
            } else {
                long new_max_not_mapped = Math.max(max_mapped, max_not_mapped);
                if (rightmost_interval[1] <= current[0]) {
                    max_mapped = 0;
                } else {
                    max_mapped = max_not_mapped + (rightmost_interval[1] - current[0]);
                }
                max_not_mapped = new_max_not_mapped;
                rightmost_interval = current;
            }
        }

        return Math.max(max_mapped, max_not_mapped);
    }

The sorting takes $O(n\log n)$ time, where $n$ is the combined size of $I_1$ and $I_2$. Since each iteration in the for loop takes no more than some constant time, the for loop takes $O(n)$ time. So the whole algorithm runs in $O(n\log n)$ time.

To find the actual partial map that produces the maximum overlap (i.e., the maximum matching between $I_1$ and $I_2$), add variables and steps to keep track of that partial map. The added steps will not change the time-complexity analysis above.

$\endgroup$

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.