假设数组通过已经排序（这是一个合理的假设，因为你从两个 1D 网格开始），我有一个解决方案是其中和是各自的大小数组。我在 MATLAB/Octave 中编写了代码，但应该很容易转换为 Python。$\mathcal{O}(n+m)$$n$$m$

% Compare two arrays for overlaps
% Test 1 - Easy
%arr1 = [0 1 2 3 4];
%arr2 = [0 1.5 3.2 5];

% Test 2 - Harder (broke the first version of the code)
arr1 = -10:10;
arr2 = [0 1.5 3.2 5];

ptr = 1; curr = ptr;
for i=1:length(arr1)-1
    while ptr<length(arr2)
        begin1 = arr1(i); end1 = arr1(i+1);
        begin2 = arr2(ptr); end2 = arr2(ptr+1);
    
        if (begin2<=end1)
            fprintf("Overlap found between %d-th interval of first set and %d-th interval of the second set\n",i,ptr);
            fprintf("Overlap length: %g\n", abs(min(end2,end1)-max(begin2,begin1)))
            curr = ptr;
            ptr = ptr + 1;
        else
            break
        end
    end
    if (end2>end1)
        ptr=max(ptr-1,curr);
    end
end

编辑：1个“如果”条件放错了地方并引入了一个错误。我认为它现在工作正常。可能需要进行测试。

编辑 2：添加 curr 变量以防止由测试 2 引起的越界访问问题。

# Python Code
import numpy as np
import time


def overlap(min1, max1, min2, max2):
    #-find overlap of two segments
    return max(0, min(max1, max2) - max(min1, min2))

def grid_overlap(grid1, grid2):
    #-calculate overlap between cells of two 1D grids
    ngrid1=len(grid1[0,:])
    ngrid2=len(grid2[0,:])

    ovlap=np.zeros([ngrid1,ngrid2])
    
    for i in range(0,ngrid1):
        for j in range(0,ngrid2):
            ovlap[i,j] = overlap(grid1[0,i], grid1[1,i], grid2[0,j], grid2[1,j])

    return ovlap
    
def grid_overlap_linear(grid1, grid2):
    ngrid1=len(grid1[0,:])
    ngrid2=len(grid2[0,:])
    
    ovlap=np.zeros([ngrid1,ngrid2])
    
    ptr = 0
    curr = 0
    
    for i in range(0,ngrid1):
        while ptr<ngrid2:
            if grid2[0,ptr] <= grid1[1,i]:
                ovlap[i,ptr] = overlap(grid1[0,i],grid1[1,i],grid2[0,ptr],grid2[1,ptr])
                
                curr = ptr
                ptr = ptr + 1
            else:
                break
        if grid2[1,ptr-1]>grid1[1,i]:
            ptr = np.max([ptr-1,curr])
            
    return ovlap


def make_1D_grid(ngrid):
    #-generate a 1D grid as a 2D array combining left and right boundaries of cells
    
    #generate a random monotonic sequence
    arr = np.sort(np.random.rand(ngrid+1))
    left = arr[0:ngrid]
    right = arr[1:ngrid+1]

    #-combine two 1D arrays (left,right) in a 2D array
    grid=np.concatenate([[left],[right]])
    
    return grid

def test_grid_overlap(n1=5, n2=3, show=False):
    #-see how it all works

    grid1 = make_1D_grid(n1)
    grid2 = make_1D_grid(n2)


    start=time.time()
    res = grid_overlap(grid1, grid2)
    end=time.time()    
    print ("Time elapsed:", end - start)
    
    start=time.time()
    res2 = grid_overlap_linear(grid1, grid2)
    end=time.time()    
    print ("Time elapsed:", end - start)

    
    
    if show:
        print("grid1:")
        print(grid1)

        print("grid2:")
        print(grid2)

        print("overlap:")
        print(res)

        print("overlap2:")
        print(res2)
        
        print(np.linalg.norm(res-res2))
        
        
test_grid_overlap(n1=50, n2=30, show=True)

编辑 3：添加了基于 Maxim Umansky 代码的 Python 版本。比较输出以检查我建议的算法是否与简单算法一致，并通过测量花费的时间来简单地检查复杂性。对于小输入（n1=5，n2=3），简单算法的性能更好。但优化的算法似乎是$\mathcal{O}(n+m)$. 输出矩阵 res 和 res2 在 10 次随机测试中匹配（$\| res-res2\| = 0$）。