python - 在 Python 中合并重叠区间

标签 python algorithm data-structures merge overlap

<分区>

我正在尝试解决一个需要合并重叠间隔的问题。 The question is :

Given a collection of intervals, merge all overlapping intervals.

For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

我尝试了我的解决方案:

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        start = sorted([x.start for x in intervals])
        end = sorted([x.end for x in intervals])
        
        merged = []
        j = 0
        new_start = 0
        
        for i in range(len(start)):
            if start[i]<end[j]:
                continue
            else:
                j = j + 1
                merged.append([start[new_start], end[j]])
                new_start = i
        
        return merged

但是它显然缺少最后一个间隔:

Input : [[1,3],[2,6],[8,10],[15,18]]

Answer :[[1,6],[8,10]]

Expected answer: [[1,6],[8,10],[15,18]]

不确定如何包括最后一个间隔，因为重叠只能在正向模式下检查。

如何修复我的算法以使其工作到最后一个时隙？

最佳答案

您的代码已经隐含地假定要对开始和结束进行排序，因此可以忽略该排序。要看到这一点，请尝试以下间隔:

intervals = [[3,9],[2,6],[8,10],[15,18]]
start = sorted([x[0] for x in intervals])
end = sorted([x[1] for x in intervals]) #mimicking your start/end lists
merged = []
j = 0
new_start = 0

for i in range(len(start)):
    if start[i]<end[j]:
        continue
    else:
        j = j + 1
        merged.append([start[new_start], end[j]])
        new_start = i
print(merged) #[[2, 9], [8, 10]]

无论如何，最好的方法可能是递归，这里显示的是列表的列表而不是 Interval 对象。

def recursive_merge(inter, start_index = 0):
    for i in range(start_index, len(inter) - 1):
        if inter[i][1] > inter[i+1][0]:
            new_start = inter[i][0]
            new_end = inter[i+1][1]
            inter[i] = [new_start, new_end]
            del inter[i+1]
            return recursive_merge(inter.copy(), start_index=i)
    return inter    

sorted_on_start = sorted(intervals)
merged = recursive_merge(sorted_on_start.copy())
print(merged) #[[2, 10], [15, 18]]

关于python - 在 Python 中合并重叠区间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49071081/

上一篇：algorithm - 如何根据操作数计算时间复杂度

下一篇：python - 二叉树中的最大和路径

python - 带有 TFIDF 的 Spark MLLIB K-means 中的索引超出范围用于文本杂乱

algorithm - 具有加权过滤器的字符串的模式识别算法？

java - 类似字典的数据结构。这是一个好习惯吗？

java - 存储矩阵值以供以后访问的更好方法

Python 链表搜索

python - 如何使用 Wikipedia API 获取图像标题

python - KDB+/q :What is a canonical implementation of a remote query?

python - 如何在字典数组中查找项目？

algorithm - 将抛物线拟合到一组点的最快方法？