Python中两个范围列表的交集

Question

我的一个朋友通过了我最近得到的一个面试问题,我对解决方案的态度不太满意.问题如下:

• 你有两个清单.
• 每个列表将包含长度为2的列表,其表示范围(即,[3,5]表示范围从3到5,包括3和5).
• 您需要返回集合之间所有范围的交集.如果我给你[1,5]和[0,2],结果将是[1,2].
• 在每个列表中,范围将始终增加并且从不重叠(即,[[0,2],[5,10] ...]永远不会[[0,2],[2,5] ......] )

一般而言,在列表的排序或重叠方面没有"陷阱".

例:

a = [[0, 2], [5, 10], [13, 23], [24, 25]]
b = [[1, 5], [8, 12], [15, 18], [20, 24]]

预期产量: [[1, 2], [5, 5], [8, 10], [15, 18], [20, 24]]

我的懒惰解决方案涉及将范围列表扩展为整数列表,然后执行集合交集,如下所示:

def get_intersection(x, y):
    x_spread = [item for sublist in [list(range(l[0],l[1]+1)) for l in x] for item in sublist]
    y_spread = [item for sublist in [list(range(l[0],l[1]+1)) for l in y] for item in sublist]
    flat_intersect_list = list(set(x_spread).intersection(y_spread))
...

但我想有一个既可读也有效的解决方案.

如果你不介意,请解释你如何在心理上解决这个问题.时间/空间复杂性分析也会有所帮助.

谢谢

Answer 1

[[max(first[0], second[0]), min(first[1], second[1])] 
  for first in a for second in b 
  if max(first[0], second[0]) <= min(first[1], second[1])]

列表理解给出了答案: [[1, 2], [5, 5], [8, 10], [15, 18], [20, 23], [24, 24]]

打破它:

[[max(first[0], second[0]), min(first[1], second[1])] 

第一学期的最大值,第二学期的最小值

for first in a for second in b 

对于第一和第二学期的所有组合:

if max(first[0], second[0]) <= min(first[1], second[1])]

仅当第一个的最大值不超过第二个的最小值时.

如果你需要压缩输出,那么下面的函数会这样做(O(n^2)及时,因为从列表中删除O(n),我们执行的步骤O(n)次数):

def reverse_compact(lst):
    for index in range(len(lst) - 2,-1,-1):
        if lst[index][1] + 1 >= lst[index + 1][0]:
            lst[index][1] = lst[index + 1][1]
            del lst[index + 1]  # remove compacted entry O(n)*
    return lst

它加入触摸的范围,因为它们是有序的.它是相反的,因为我们可以在适当的位置执行此操作并删除压缩的条目.如果我们没有反向执行,删除其他条目将会破坏我们的索引.

>>> reverse_compact(comp)
[[1, 2], [5, 5], [8, 10], [15, 18], [20, 24]]

• O(n)通过进行正向压缩和复制元素,可以进一步减少压缩功能,因为每个内部步骤都是O(1)(get/set而不是del),但这样可读性较差:

这在O(n)时间和空间复杂性上运行:

def compact(lst):
    next_index = 0  # Keeps track of the last used index in our result
    for index in range(len(lst) - 1):
        if lst[next_index][1] + 1 >= lst[index + 1][0]:
            lst[next_index][1] = lst[index + 1][1]
        else:    
            next_index += 1
            lst[next_index] = lst[index + 1]
    return lst[:next_index + 1]

使用压缩器,列表理解是这里的主导术语,time = O(n*m),space = O(m+n),因为它比较了两个列表的所有可能组合而没有提前出局.这并没有利用提示中给出的列表的有序结构:您可以利用该结构来减少时间复杂度,O(n + m)因为它们总是增加并且从不重叠,这意味着您可以在一次通过中进行所有比较.

请注意,有多个解决方案,希望您可以解决问题,然后迭代地改进它.

满足所有可能输入的100%正确答案不是面试问题的目标.它是为了了解一个人如何思考和处理挑战,以及他们是否可以推理解决方案.

事实上,如果你给我一个100%正确的教科书答案,那可能是因为你之前已经看过这个问题并且你已经知道了解决方案......因此这个问题对我作为面试官没有帮助."检查,可以反驳StackOverflow上的解决方案." 我们的想法是看你解决问题,而不是反复解决问题.

太多的候选人错过了森林的树木:承认缺点并提出解决方案是回答面试问题的正确方法.您不必拥有解决方案,您必须展示如何解决问题.

如果您可以解释它并详细说明使用它的潜在问题,那么您的解决方案就可以了

我没有回答一个面试问题而得到了我现在的工作:在我大部分时间都在尝试之后,我解释了为什么我的方法不起作用,而第二种方法我会尝试给予更多时间,以及我在那看到的潜在陷阱方法(以及为什么我最初选择了我的第一个策略).

Answer 2

OP,我相信这个解决方案有效,它运行在O(m + n)时间,其中m和n是列表的长度.(当然,请创建ranges一个链表,以便在不变的时间内更改其长度.)

def intersections(a,b):
    ranges = []
    i = j = 0
    while i < len(a) and j < len(b):
        a_left, a_right = a[i]
        b_left, b_right = b[j]

        if a_right < b_right:
            i += 1
        else:
            j += 1

        if a_right >= b_left and b_right >= a_left:
            end_pts = sorted([a_left, a_right, b_left, b_right])
            middle = [end_pts[1], end_pts[2]]
            ranges.append(middle)

    ri = 0
    while ri < len(ranges)-1:
        if ranges[ri][1] == ranges[ri+1][0]:
            ranges[ri:ri+2] = [[ranges[ri][0], ranges[ri+1][1]]]

        ri += 1

    return ranges

a = [[0,2], [5,10], [13,23], [24,25]]
b = [[1,5], [8,12], [15,18], [20,24]]
print(intersects(a,b))
# [[1, 2], [5, 5], [8, 10], [15, 18], [20, 24]]

Answer 3

Algorithm

Given two intervals, if they overlap, then the intersection's starting point is the maximum of the starting points of the two intervals, and its stopping point is the minimum of the stopping points:

To find all the pairs of intervals that might intersect, start with the first pair and keep incrementing the interval with the lower stopping point:

At most m + n pairs of intervals are considered, where m is length of the first list, and n is the length of the second list. Calculating the intersection of a pair of intervals is done in constant time, so this algorithm's time-complexity is O(m+n).

Implementation

To keep the code simple, I'm using Python's built-in range object for the intervals. This is a slight deviation from the problem description in that ranges are half-open intervals rather than closed. That is,

(x in range(a, b)) == (a <= x < b)

Given two range objects x and y, their intersection is range(start, stop), where start = max(x.start, y.start) and stop = min(x.stop, y.stop). If the two ranges don't overlap, then start >= stop and you just get an empty range:

>>> len(range(1, 0))
0

So given two lists of ranges, xs and ys, each increasing in start value, the intersection can be computed as follows:

def intersect_ranges(xs, ys):

    # Merge any abutting ranges (implementation below):
    xs, ys = merge_ranges(xs), merge_ranges(ys)

    # Try to get the first range in each iterator:
    try:
        x, y = next(xs), next(ys)
    except StopIteration:
        return

    while True:
        # Yield the intersection of the two ranges, if it's not empty:
        intersection = range(
            max(x.start, y.start),
            min(x.stop, y.stop)
        )
        if intersection:
            yield intersection

        # Try to increment the range with the earlier stopping value:
        try:
            if x.stop <= y.stop:
                x = next(xs)
            else:
                y = next(ys)
        except StopIteration:
            return

It seems from your example that the ranges can abut. So any abutting ranges have to be merged first:

def merge_ranges(xs):
    start, stop = None, None
    for x in xs:
        if stop is None:
            start, stop = x.start, x.stop
        elif stop < x.start:
            yield range(start, stop)
            start, stop = x.start, x.stop
        else:
            stop = x.stop
    yield range(start, stop)

Applying this to your example:

>>> a = [[0, 2], [5, 10], [13, 23], [24, 25]]
>>> b = [[1, 5], [8, 12], [15, 18], [20, 24]]
>>> list(intersect_ranges(
...     (range(i, j+1) for (i, j) in a),
...     (range(i, j+1) for (i, j) in b)
... ))
[range(1, 3), range(5, 6), range(8, 11), range(15, 19), range(20, 25)]