相关疑难解决方法(0)

我有一个元组列表,每个元组都是一个元组(start-time, end-time).我正在尝试合并所有重叠的时间范围并返回不同时间范围的列表.例如

[(1, 5), (2, 4), (3, 6)] --->  [(1,6)]
[(1, 3), (2, 4), (5, 8)] --->  [(1, 4), (5,8)]

这是我实现它的方式.

# Algorithm
# initialranges: [(a,b), (c,d), (e,f), ...]
# First we sort each tuple then whole list.
# This will ensure that a<b, c<d, e<f ... and a < c < e ... 
# BUT the order of b, d, f ... is still random
# Now we have only 3 possibilities
#================================================
# b<c<d: a-------b           Ans: …

我试图找到解决以下问题的最佳方法.最好的方式我的意思是不那么复杂.

作为输入,元组列表(开始,长度)如下:

[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]

每个元素通过其开始和长度来表示序列,例如(5,7)等同于序列(5,6,7,8,9,10,11)- 以5开头的7个元素的列表.可以假设元组按start元素排序.

输出应返回表示最长连续序列的非重叠元组组合.这意味着,解决方案是范围的子集,没有重叠且没有间隙,并且是最长的 - 尽管可能不止一个.

例如,对于给定的输入,解决方案是:

[(0,5),(5,7)] 相当于 (0,1,2,3,4,5,6,7,8,9,10,11)

它是回溯解决这个问题的最佳方法吗？

我对人们可以建议的任何不同方法感兴趣.

此外,如果有人知道这个问题的正式参考或另一个类似的问题,我想得到参考.

顺便说一句 - 这不是功课.

编辑

为了避免一些错误,这是预期行为的另一个例子

对于[(0,1),(1,7),(3,20),(8,5)]正确答案的输入[(3,20)]相当于(3,4,5,...,22)长度为20.收到的一些答案[(0,1),(1,7),(8,5)]相当于(0,1,2,...,11,12)作为正确答案.但这最后的答案是不正确的,因为它比短于[(3,20)].