Python中两个范围列表的交集 [英] Intersection of two lists of ranges in Python

问题描述

我的一个朋友让我通过了他最近遇到的一个采访问题，而我对解决方案的方法并不满意。问题如下：

A friend of mine passed me over an interview question he recently got and I wasn't very happy with my approach to the solution. The question is as follows:

• 您有两个列表。


• 每个列表将包含长度为2的列表，它们代表一个范围（即[3,5]表示范围是3到5，包括3和5）。


• 您需要返回集合之间所有范围的交集。如果我给您[1,5]和[0,2]，结果将是[1,2]。


• 在每个列表中，范围将始终增加且永不重叠（即它将是[[0，2]，[5，10] ...]从不[[0,2 ]，[2,5] ...]）

• You have two lists.
• Each list will contain lists of length 2, which represent a range (ie. [3,5] means a range from 3 to 5, inclusive).
• You need to return the intersection of all ranges between the sets. If I give you [1,5] and [0,2], the result would be [1,2].
• Within each list, the ranges will always increase and never overlap (i.e. it will be [[0, 2], [5, 10] ... ] never [[0,2], [2,5] ... ])

通常，在排序或重叠方面没有陷阱

In general there are no "gotchas" in terms of the ordering or overlapping of the lists.

示例：

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

我的惰性解决方案涉及将范围列表扩展为整数列表，然后进行交集，如下所示：

My lazy solution involved spreading the list of ranges into a list of integers then doing a set intersection, like this:

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

但是我想有一种既可读又高效的解决方案。

But I imagine there's a solution that's both readable and more efficient.

请解释一下，如果您不介意的话，将如何解决这个问题。时间/空间复杂度分析也将有所帮助。

Please explain how you would mentally tackle this problem, if you don't mind. A time/space complexity analysis would also be helpful.

谢谢

推荐答案

OP，我相信此解决方案有效，并且可以在O（m + n）的时间内运行，其中m和n是列表的长度。 （可以肯定的是，使范围成为链接列表，以便更改其长度以恒定的时间运行。）

OP, I believe this solution works, and it runs in O(m+n) time where m and n are the lengths of the lists. (To be sure, make ranges a linked list so that changing its length runs in constant time.)

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

这篇关于Python中两个范围列表的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！