Python:算法

Question

问题：给定无序时间戳列表，找出重叠的最大时间跨度
例如：[1,3]、[10,15]、[2,7]、[11,13]、[12,16]、[5,8]=>；[1,8]和[10,16]

我被要求解决上面的问题。在

我最初的做法是：

times = [[1,3],[10,15],[2,7],[11,13],[12,16],[5,8]]
import itertools
def flatten(listOfLists):
    return itertools.chain.from_iterable(listOfLists)
start = [i[0] for i in times]
end = [i[1] for i in times]
times = sorted(list(flatten(times)))
# 1=s, 2=s, 3=e, 5=s, 7=e, 8=e, 10=s, 11=s, 12=s, 13=e, 15=e, 16=e
num_of_e = 0
num_of_s = 0
first_s = 0
for time in times:
    if first_s == 0:
        first_s = time
    if time not in end:
        num_of_s += 1
    if time in end:
        num_of_e += 1
        if num_of_e == num_of_s:
            num_of_e = 0
            num_of_s = 0
            print [first_s, time]
            first_s = 0

然后，发问者坚持我应该先点时间来解决这个问题，因为“这样更好”，所以我做了下面的事情

^{pr2}$

是否存在“更好”的方法（或者可能是其他更好的方法）？我知道我可以计时，看看哪一个更快，或者仅仅基于大O符号（对于实际的工作部分，两者都是O（N））。在

只是想看看你们对这件事有什么看法？
你喜欢哪一个？为什么？
或者其他方法？在

Answer 1

在评估一个算法时，速度通常是最重要的考虑因素，但它可能不是唯一的考虑因素。但让我们先看看速度。在

在这种情况下，有两种速度需要考虑：渐近（这是大Ω-Θ-O符号的特征）和非渐近速度。即使两个算法具有相同的渐近行为，其中一个可能仍然比另一个好得多，因为算法中的其他成本在较小的数据量下会非常显著。在

在第一个算法中，在排序前对列表进行两次迭代，然后在排序后对列表进行第三次迭代。在第二个答案中，您只迭代列表一次。我希望第二个速度更快，但是在Python中，性能有时会令人惊讶，因此如果需要速度，最好测量一下。在

你也可以评估一个算法对内存的使用。第一个算法创建两个开始时间和结束时间的临时列表，第三个临时列表保存排序后的时间跨度。如果数据集很大的话，这些可能会很昂贵！第二个算法避免了这一点，但是每次调用merge时都会创建一个长度为2的新列表。这可能仍然是分配的大量内存，可能需要进一步优化。在幕后还可能隐藏着一些内存使用：例如，当您查看如何实现sort时，实际上使用的内存可能不会比{}少很多。在

在评估一个算法时，最后要考虑的是你的受众。例如，如果你正在面试，速度和记忆力对于你第一次尝试实现一个算法来说可能不像清晰和风格那么重要。在

Answer 2

以下是一个关于规避time in end时间计算和具体案例问题相关风险的建议：

times = [[1,3],[10,15],[2,7],[11,13],[12,16],[5,8]]
start = [(i[0], 0) for i in times]
end = [(i[1], 1) for i in times]
# Using 0 for start and 1 for end ensures that starts are resolved before ends
times = sorted(start + end)
span_count = 0
first_s = 0
for time, is_start in times:
    if first_s == 0:
        first_s = time
    if is_start == 0:
        span_count += 1
    else:
        span_count -= 1
        if span_count == 0:
            print [first_s, time]
            first_s = 0

而且，它有一个易于计算的复杂度O(n) (actual work) + O(n*log(n)) (sort) = O(n*log(n))