我正在尝试找到解决以下问题的最佳方法。最好的方法是说不太复杂。
作为输入的元组列表（开始，长度），例如：
[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]
每个元素都以其 开始 和 长度 重新设置 一个序列，例如（5,7）等同于该序列(5,6,7,8,9,10,11)-以5开头的7个元素的列表。可以假定元组按start元素排序。
(5,6,7,8,9,10,11)
start
输出应返回表示最长连续序列的元组的非重叠组合。这意味着，解决方案是范围的子集，没有重叠且没有缺口，并且可能的最长-尽管可能有多个。
例如，对于给定的输入，解决方案是：
[(0,5),(5,7)] 相当于 (0,1,2,3,4,5,6,7,8,9,10,11)
[(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)]等于长度为20的（3,4,5，..，22）。收到的某些答案将[(0,1),(1,7),(8,5)]等于（0,1,2，…，11,12）作为正确的答案。但是最后一个答案不正确，因为它比短[(3,20)]。
[(0,1),(1,7),(3,20),(8,5)]
[(3,20)]
[(0,1),(1,7),(8,5)]
使用给定的顺序（通过start元素）遍历元组列表，同时使用哈希图跟踪以某个索引 结尾 的最长连续序列的长度。
伪代码，跳过诸如在哈希图中找不到的项目之类的详细信息（假设未找到，则返回0）：
int bestEnd = 0; hashmap<int,int> seq // seq[key] = length of the longest sequence ending on key-1, or 0 if not found foreach (tuple in orderedTuples) { int seqLength = seq[tuple.start] + tuple.length int tupleEnd = tuple.start+tuple.length; seq[tupleEnd] = max(seq[tupleEnd], seqLength) if (seqLength > seq[bestEnd]) bestEnd = tupleEnd } return new tuple(bestEnd-seq[bestEnd], seq[bestEnd])
这是一个O（N）算法。
如果您需要实际的元组组成此序列，则还需要保留一个由结束索引散列的元组链接列表，并在为此端点更新最大长度时进行更新。
更新：我对python的了解非常有限，但是基于您粘贴的python代码，我创建了以下代码，该代码返回实际序列而不是长度：
def get_longest(arr): bestEnd = 0; seqLengths = dict() #seqLengths[key] = length of the longest sequence ending on key-1, or 0 if not found seqTuples = dict() #seqTuples[key] = the last tuple used in this longest sequence for t in arr: seqLength = seqLengths.get(t[0],0) + t[1] tupleEnd = t[0] + t[1] if (seqLength > seqLengths.get(tupleEnd,0)): seqLengths[tupleEnd] = seqLength seqTuples[tupleEnd] = t if seqLength > seqLengths.get(bestEnd,0): bestEnd = tupleEnd longestSeq = [] while (bestEnd in seqTuples): longestSeq.append(seqTuples[bestEnd]) bestEnd -= seqTuples[bestEnd][1] longestSeq.reverse() return longestSeq if __name__ == "__main__": a = [(0,3),(1,4),(1,1),(1,8),(5,2),(5,5),(5,6),(10,2)] print(get_longest(a))
