如何计算两个（价格，时间）元素数组的重叠时间

Question

我在工作中很难想出一种基本上计算以下内容的算法

假设你有两个数组。数组中的每个元素包含价格和时间。每个数组都按时间升序排序。例如，array1 = [(10, 1), (5, 2), (7, 4)] 表示从时间 = 1 到 2 的价格 = 10，从时间 = 2 到 4 的价格 = 5，从时间 = 2 到 4 的价格 = 7 = 4. 计算绝对价格差为 <= 10.

的 2 个数组的总重叠时间

举个例子，假设我们有

array1 = [(10, 1), (5, 2), (7, 4)]

array2 = [(19, 0), (6, 2), (23, 4)]

这里的重叠时间是3。从time=1到time=4（不包含），差值是<= 10. For the time interval [0, 1), the price difference is undefined and does not contribute to the overlap time. For the interval [1, 2), the price difference is < 10 and ditto for [2, 4). So they have a price diff < 10 for the interval [1, 4), hence the answer is 3.

（如果将其绘制在 x-y 图上并查看 2 条线的 y 值何时存在差异，则更容易可视化 <= 10 for the same x value).

我尝试了几种循环间隔的算法，但总是设法错过一些边缘情况。诚然，我不擅长这类区间合并问题（我认为有一个特定的词可以描述此类问题，但我不记得了）。有哪些万无一失的方法可以解决这个问题？

我觉得我应该以一种特殊的方式来思考这个问题，这将使实施变得微不足道，但显然我并没有那样考虑。

Answer 1

这个想法是按排序顺序（按时间）访问两个输入数组中的条目：每当您可以从任一数组中进行选择时，请选择时间最少的项目，然后移至所选数组中的下一个项目，因此在下一次迭代中，

那个项目可以按其时间进行比较。

一旦实现了遍历，您就可以遍历商品，直到获得两个来源的价格，并在遍历过程中比较差异。

这是 Python 中的实现：

# Merge two sorted price-evolution lists in sorted order
def merged(list1, list2):
    iters = (iter(list1), iter(list2))
    val = [next(iters[0], None), next(iters[1], None)]
    while val[0] is not None or val[1] is not None:
        i = val[0] is None or val[1] is not None and val[0][1] > val[1][1]
        yield i, val[i]
        val[i] = next(iters[i], None)

def overlap_time(list1, list2, maxdiff):
    prices = {}  # To keep track of last price per source-list
    result = 0
    # Iterate the price change events in chronological order
    for source, (price, time) in merged(list1, list2):
        # Do we have prices from both source lists and are they close?
        if len(prices) == 2 and abs(prices[0] - prices[1]) <= maxdiff:
            result += time - prevtime
        prices[source] = price
        prevtime = time
    return result

调用示例：

list1 = [(10, 1), (5, 2), (7, 4)]
list2 = [(19, 0), (6, 2), (8, 4), (28, 8)]
print(overlap_time(list1, list2, 10))  # 3