在Python中合并重叠间隔 [英] Merging Overlapping Intervals in Python

问题描述

我正在尝试解决一个需要合并重叠间隔的问题: https://leetcode.com/problems/merge-intervals/description/

I am trying to solve a question wherein overlapping intervals need to be merged: https://leetcode.com/problems/merge-intervals/description/

问题是:

给出间隔的集合，合并所有重叠的间隔.

Given a collection of intervals, merge all overlapping intervals.

例如，给定[1,3]，[2,6]，[8,10]，[15,18]，返回[1,6]，[8,10]，[15,18].

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

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

However it is clearly missing the last interval as:

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

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

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

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

Not sure how to include the last interval as overlap can only be checked in forward mode.

如何修复我的算法，使其在最后一个时隙之前都能正常工作?

How to fix my algorithm so that it works till the last slot?

感谢您的帮助.

推荐答案

您的代码已经隐式假定要对开始和结束进行排序，因此可以省略排序.要查看此消息，请尝试以下间隔:

Your code implicitly already assumes the starts and ends to be sorted, so that sort could be left out. To see this, try the following intervals:

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对象.

Anyway, the best way to do this is probably recursion, here shown for a list of lists instead of Interval objects.

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中合并重叠间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！