想象两个段落，用元组中的发言秒表示。例如，在第566秒到第579秒之间说话。
<标题>老例子passage1 = (566,579),(573,583.33)
passage2 = (574,579.21),(614,620)
=比;十字路口(574579 .21)
<标题>新例子passage1 = (566,579),(570,590)
passage2 = (572,575),(577,620)
=比;路口(572,575)(577,590)
找到这些片段之间交集的最有效方法是什么?我如何在python中表示时间?我对任何想法都持开放态度，因为我还没有找到任何方法来表示它并进行计算。
首先，对每个段落中的间隔进行排序，确保它们按照开始时间的顺序排列，并合并每个段落中任何重叠的间隔。
passage1 = (566,579),(573,583.33)
passage2 = (574,579.21),(614,620)
passage3 = (566,579),(570,590)
passage4 = (572,575),(577,620)
def merge_overlapping_intervals(intervals):
intervals = iter(sorted(intervals))
start, end = next(intervals)
for next_start, next_end in intervals:
if next_start <= end <= next_end:
end = next_end
else:
yield start, end
start = next_start
end = next_end
yield start, end
print(list(merge_overlapping_intervals(passage1))) # 566, 583.33
然后，找出段落1中的间隔与段落2中的间隔之间的所有重叠:
def interval_overlaps(intervals1, intervals2):
""" Yield all overlaps of intervals in sequence intervals1 with intervals in sequence intervals2 """
for start1, end1 in merge_overlapping_intervals(intervals1):
for start2, end2 in merge_overlapping_intervals(intervals2):
if end1 > start2 and end2 > start1:
yield max(start1, start2), min(end1, end2)
print(list(interval_overlaps(passage1, passage2))) # [(574, 579.21)]
print(list(interval_overlaps(passage3, passage4))) # [(572, 575), (577, 590)]
同样地，您可以首先识别所有重叠，然后然后对它们进行排序并合并任何重叠的重叠。
由于嵌套循环，其时间效率为O(nm)，其中n和m为每条通道的段数。考虑到段落是排序的，应该有一种更省时的算法来识别重叠，但需要更多的思考来编写，我想可能不需要。
判断两个段是否相交是很容易的。如果其中一个的结束在另一个的开始之前，它们不相交。
一旦你知道他们相交,交点本身就是微不足道的决定——这是早些时候的后两个开始时间和结束时间。注意，这可能导致零长度段。
现在您可以简单地遍历passe1中的每个片段，并对照passe2中的所有片段进行检查。但这将是一个缓慢的O(n²)算法(假设两个序列具有相同的长度n)，并且您对效率感兴趣。
既然你在评论中说，每个序列中的片段将是不重叠的，我们可以使用该信息来找到一个更有效的算法。我们可以为每个通道生成一个排序的开始和停止事件的时间轴，当你有一个开始和一个停止的时间段代表一个交叉点。不幸的是，你在问题中给出的示例数据不符合约束，所以我不确定这是否会起作用。
编辑:我看到你已经改变了例子，以满足约束，所以现在它实际工作。因为这个问题，我没有发表这篇文章。
def intersections(seq1, seq2):
events = sorted([(s, False, 0) for s,e in seq1] +
[(e, True, 0) for s,e in seq1] +
[(s, False, 1) for s,e in seq2] +
[(e, True, 1) for s,e in seq2])
starts = [None, None]
for time, end_flag, seq_num in events:
if end_flag:
if (starts[0] is not None) and (starts[1] is not None):
yield max(starts), time
starts[seq_num] = None
else:
starts[seq_num] = time
>>> for s,e in intersections(passage1, passage2):
print(s, e)
572 575
577 579