给定两个排序的间隔列表，返回两个列表之间的重叠间隔 [英] Given two sorted lists of intervals, return the overlapping intervals between the two lists

问题描述

为您提供了两个间隔列表，分别为 A 和 B 。

You are given two lists of intervals, A and B.

在 A 中，间隔按其起点排序。 A 内的间隔都没有重叠。

In A, the intervals are sorted by their starting points. None of the intervals within A overlap.

同样，在 B ，间隔按其起点排序。 B 中的间隔都没有重叠。

Likewise, in B, the intervals are sorted by their starting points. None of the intervals within B overlap.

返回两个列表之间重叠的间隔。

Return the intervals that overlap between the two lists.

例如：

A: {[0,4], [7,12]}
B: {[1,3], [5,8], [9,11]}

返回：

{[1,3], [7,8], [9,11]} 

我在一次采访中发现了这个问题，并为此感到沮丧。

I got this in an interview and was stumped.

我想到了比较两个列表之间的间隔。如果两者之间存在重叠，则将重叠添加到结果列表中。然后，我以较小的开始间隔来推进列表的指针，但到面试结束时仍无法找到可行的解决方案。

I thought of comparing intervals between the two lists. If there is an overlap between the two, add the overlap to a results list. I then advance the pointer of the list with the smaller starting interval but was unable to get to a working solution by the end of the interview.

什么是最好的方法解决这个问题？

What is the best way to solve this problem?

推荐答案

这是一个遵循罗马原则divit-et-impera的实现：

Here is an implementation, following the roman principle divide-et-impera:

首先，找到一个方法，该方法对于给定的Interval对，找到重叠（如果有）。

First, find a method, which, for a given pair of Intervals, finds the overlap, if any.

/* Cases: A behind B, A overlap at start, A part of B, B part of A,
   overlap at end, B starts after A ended:
A:    2..3..4..5
Bs:   |        | 
0..1  |        |
0..1..2..3     |
0..1..2..3..4..5..6
      |  3..4  |
      |     4..5..6
      |        |  6..7
*/
case class Interval (lower: Int, upper: Int) {
    def overlap (other: Interval) : Option [Interval] = {
        if (lower > other.upper || upper < other.lower) None else 
        Some (Interval (Math.max (lower, other.lower), Math.min (upper, other.upper)))
    }
}

这是确定责任的方法，两个间隔。

That was the method with a limited responsibility, to decide for two Intervals.

如果您不熟悉Scala：Interval是一个类，第一行可以看做构造函数。上下应该是自我解释的（Int类型）。
该类具有一个方法重叠，该方法接受该类的另一个实例（另一个），并因此返回一个新的重叠间隔。但是包装在一个Option中，这意味着：如果没有发现重叠，我们将返回None。如果找到一个，则为Some（间隔）。您可以帮助自己将其理解为一个列表，该列表可以为空或仅包含一个元素。通过发信号通知使用Type可能没有结果，这是一种避免NullpointerException的技术。

If you're not familiar with Scala: Interval is a class, and the first line can be read as constructor. Lower and upper should be self explaining (of type Int). The class has a method overlap, which takes a second instance of the class (other) and returns, as a result, a new Interval of the overlapping. But wrapped into an Option, which means: If no overlap is found, we return None. If we find one, it is Some (Interval). You can help yourself to understand this construct as a List, which is either empty, or contains exactly one element. It's a technique to avoid NullpointerException, by signalling, that there might be no result, with a Type.

如果一个时间间隔的上限值低于另一个时间间隔的下限值，则不会有重叠，因此我们返回None。

If the upper of the one Interval is lower than the lower of the other interval, there can't be an overlap, so we return None.

对于重叠，我们将两个下限中的最大值作为下限，将两个上限中的最小值作为新上限。

For the overlap, we take the maximum of the two lower bounds as lower bound, and the minimum of the two upper bounds, as new upper bound.

数据：

val a = List (Interval (0, 4), Interval (7, 12))
val b = List (Interval (1, 3), Interval (5, 8), Interval (9, 11))

天真的方法：气泡重叠（首先使其起作用，然后使其快速）：

Naive approach: Bubble overlap (first make it work, then make it fast):

scala> a.map (aa => b.map (bb => aa.overlap (bb))).flatten.flatten
res21: List[Interval] = List(Interval(1,3), Interval(7,8), Interval(9,11))

核心（如果不使用）可能会有助于理解的Option /也许带有Some（T）和None的是：

The core, if you're not used to Option/Maybe with Some(T) and None, which might help to understand, is:

a.map (aa => b.map (bb => aa.overlap (bb))) 
res19: List[List[Option[Interval]]] = List(List(Some(Interval(1,3)), None, None), List(None, Some(Interval(7,8)), Some(Interval(9,11))))

第一个拼合将两个内部List合并为一个List，第二个拼合去除了None，并给我们留了Intervals，而不是包装Some（Interval）。

The first flatten combined the two inner Lists into one List, and the second flatten removed the Nones and left us with Intervals, instead of the wrapper Some(Interval).

也许我可以提出一个迭代的解决方案，该解决方案的间隔不超过它匹配的2倍。
...（10分钟后）...
这是：

Maybe I can come up with an iterative solution, which takes no interval more than 2 times more often, than it matches. ...(10 min later)... Here it is:

def findOverlaps (l1: List[Interval], l2: List[Interval]): List[Option[Interval]] = (l1, l2) match {
    case (_, Nil) => Nil 
    case (Nil, _) => Nil
    case (a :: as, b :: bs) => {
             if (a.lower > b.upper) findOverlaps (l1, bs) 
        else if (a.upper < b.lower) findOverlaps (as, l2) 
        else if (a.upper > b.upper) a.overlap (b) :: findOverlaps (l1, bs) 
        else                        a.overlap (b) :: findOverlaps (as, l2) 
    }
}

前两个内行检查，如果两个列表中的任何一个为空，则不再显示可以预期会有重叠。

The first two inner lines check, if either of the Lists is empty - then no more overlap can be expected.

（a :: as，b :: bs）是（l1，l2的匹配项）a是l1的头部，因为l1的尾部（可能是Nil），并且类似物b是l2的开头，b是其尾部。

(a :: as, b :: bs) is a match of (l1, l2) a is the head of l1, as the tail of l1 (might be Nil) and analog b is the head of l2, bs its tail.

如果a.lower大于b.upper，我们取b列表的尾部并重复如果b.lower> a.upper，则递归地处理整个l1-list以及类似的内容，包括整个l2-List，但只有l1列表的尾部。

If a.lower is > b.upper, we take the tail of the b list and repeat recursively with the whole l1-list and similar, with the whole l2-List but only the tail of the l1 list, if b.lower > a.upper.

Else我们应该有一个重叠，因此在两种情况下我们都应使用a.overlap（b），其中一个列表的整个列表具有较高的上限，而另一个列表的末尾。

Else we should have an overlap so we take a.overlap (b) in either case, with the whole list of the one with higher upper bound, and the tail of the other list.

scala> findOverlaps (a, b)
res0: List[Option[Interval]] = List(Some(Interval(1,3)), Some(Interval(7,8)), Some(Interval(9,11)))

您看到的是，没有生成任何内容，对于findOverlaps（b，a），结果相同

You see, no None was generated, and for findOverlaps (b, a) the same result.

这篇关于给定两个排序的间隔列表，返回两个列表之间的重叠间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！