Python列表操作: Given a list of ranges number,返回组合范围的列表

Question

我在电话面试时遇到了这个问题:

Suppose there is a list of ranges. For example, [[1-6],[10-19],[5-8]]. Write a function that returns the list of combined ranges such that input [[1-6],[10-19],[5-8]] to the function returns [[1,8],[10,19]] (only the start and end number). Note, the input list may contain arbitrary number of ranges.

我解决这个问题的方法是:

1. 将所有范围列表合并为一个列表: [[1-6],[10-19],[5-8]] -> [1-6,10-19,5-8]

2. 对列表进行排序: 列表 = 排序(列表)-> [1,2,3,4,5,5,6,6,7,8,10...]

3. 使用 list = set(list) 去掉多余的数字

4. 迭代列表并找到范围

我知道这个解决方案绝对是他们正在寻找的(这就是我面试失败的原因)，因为时间复杂度是 O(nlogn) (排序)，n 是范围内不同数字的数量。

Python专家能否给出一个O(n)的解决方案，n为原始列表中的范围数？

Answer 1

首先，问题中提到的解决方案不是O(nlgn)，其中n是段数。这是 O(Xlg(X))，其中 X = length of the segment*num of segments ，这非常慢。 存在 O(NlgN) 解，其中 N 是段数。

1. 按起点对片段进行排序。
2. 扫描已排序的列表并检查当前段是否与前一个段重叠。如果是，则根据需要扩展前一段。

示例代码:

inp = [[1,6], [10,19], [5,8]]

inp = sorted(inp)
segments = []

for i in inp:
    if segments:
        if segments[-1][1] >= i[0]:
            segments[-1][1] = max(segments[-1][1], i[1])
            continue
    segments.append(i)

print segments # [[1, 8], [10, 19]]