Weighted maximum match for intervals

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 I_2$ without taking into account the length of the overlap

• 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?

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.

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

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

-
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 = 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]

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.

StackExchange Computer Science Q#144799, answer score: 2