python - 从范围集合返回最小范围数的最佳方法

Question

一般来说，我是 Python 和 SWE 的新手，所以请原谅简单的问题。一位面试官向我提出了以下编码挑战。我想出了以下解决方案。但是我被忽略了，因为它不符合他们的性能标准。我想知道是否有人可以指导我如何在这个问题上以及在一般情况下如何更好地解决此类问题。我找到了解决该问题的其他答案，但我想要针对我的实现的具体答案。

这是我收到的反馈:

1. while (zip_range_list):线条突出:你看不到很多Python 中的 while 循环，你不必在循环的两边加上括号测试表达式，用 while 循环解决这个问题是奇怪的事情。 为什么 while 循环是个坏主意？
2. 在减少之前向 reduced_zip_ranges 添加一个范围，然后不断引用您刚刚添加的元素reduced_zip_ranges[-1] 而不是为其单独绑定(bind)读起来很笨拙。 为什么这么尴尬？
3. 构造 range_check = range(low-1, high+2) 可能是正确的，但它看起来既奇怪又荒谬地浪费空间:他没有比较端点，而是构建了一个包含整个数字范围的列表，只是为了查看该范围内的成员(member)资格。他一遍又一遍地 build 这些循环内循环。 我明白了。我试图避免长 if 语句。这不是个好主意。
4. 说到“循环中的循环”，这是一种复杂度为 O(N 平方) 的算法，而排序后的复杂度可能为 O(N)。 我想我忽略了这一点，我现在看到 0(n^2)。我怎样才能避免这种情况？
5. 例程有两个不同的非异常返回点；循环中的那个是不必要的(代码在被注释掉的情况下也能正常工作)。

问题给定一组邮政编码范围(每个范围包括他们的上限和下限)，提供一种生成所需范围的最少数量的算法表示与输入相同的覆盖范围。

Input: [[14,17], [4,7], [2,5], [10,12] , [15,16], [4,9], [11,13]]
Output: [[2,17]]


# Implementation
def zip_range_reducer(zip_range_list):

    if not zip_range_list:
        raise Exception("Empty list of ranges provided!")

    reduced_zip_ranges = []

    zip_range_list.sort()

    while (zip_range_list):
        no_overlap_ranges = []
        reduced_zip_ranges.append(zip_range_list[0])
        if len(zip_range_list) == 1:
            return reduced_zip_ranges
        zip_range_list.pop(0)
        for zip_range in zip_range_list:
            low, high = reduced_zip_ranges[-1][0], reduced_zip_ranges[-1][1]
            range_check = range(low-1, high+2)
            if zip_range[0] in range_check or zip_range[1] in range_check:
                reduced_zip_ranges[-1][0] = min(reduced_zip_ranges[-1][0], zip_range[0])
                reduced_zip_ranges[-1][1] = max(reduced_zip_ranges[-1][1], zip_range[1])
            else:
                no_overlap_ranges.append(zip_range)
        zip_range_list = no_overlap_ranges

    return reduced_zip_ranges

还有

Answer 1

这是一个 O(n) 的解决方案。 [排除排序的复杂性]

def reduceRangeList(ranges):
    # sorting the list based on the lower limit, and then based on size as tie breaker
    # note we need the bigger ranges to come before the smaller ranges
    ranges.sort(key= lambda pair : (pair[0], - pair[1]))

    reduced= []     # new set of ranges are stored here

    # we use a parent range to decide if a range is inside other ranges
    parent= ranges[0]

    # this will for sure be part of the solution,
    # because it is the largest, leftmost range
    reduced.append(ranges[0])

    for x in ranges:
        if parent[0] <= x[0] and x[1] <= parent[1]:
            # this range is completely within another range, ignore!
            continue
        elif x[0] <= parent[1]:
            # this range is partially inside the parent range
            # so we set the parent to cover this two range
            parent= [parent[0], x[1]]
        else:
            #this range is completely outside the parent range
            parent= x

        # If the range is completely or partially outside other ranges...
        # I'm placing it here to avoid duplicate code
        reduced.append(x)

    return reduced




def main():
    ranges= [[1,5], [2, 4], [6, 7], [2,7], [9,10]]
    # ranges= [[1,5], [1,4], [2, 6]]
    # ranges= [[1,2], [3,4], [5,6], [1,6], [6,7], [4, 8]]


    reduced= reduceRangeList(ranges)

    print(reduced)

if __name__ == '__main__':
    main()