logo标签列表

Python中合并重叠的区间

pythonalgorithmdata-structuresmergeoverlap
5

我正在尝试解决一个问题，其中需要合并重叠的区间。

这个问题是：

给定一组区间，合并所有重叠的区间。

例如，给定 [1,3]、[2,6]、[8,10] 和 [15,18]，应返回 [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]]

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

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

1
请阅读并遵守帮助文档中的发布指南。最小化、完整化、可验证化示例适用于此处。在您发布MCVE代码并准确描述问题之前，我们无法有效地帮助您。我们应该能够将您发布的代码粘贴到一个文本文件中，并重现您描述的问题。您的示例不完整。 - Prune
6个回答
4

您的代码已经假定了开头和结尾已排序，因此可以省略排序。为了看清楚这一点，请尝试以下间隔：

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]]
1
你为什么认为第二种方法更好？那似乎比第一种慢得多，不是吗？ - Woods Chen
3

我知道这个问题很老了，但是如果有帮助的话，我写了一个Python库来处理（一组）区间。它的名字叫portion，可以轻松合并区间：

>>> import portion as P
>>> inputs = [[1,3],[2,6],[8,10],[15,18]]
>>> # Convert each input to an interval
>>> intervals = [P.closed(a, b) for a, b in inputs]
>>> # Merge these intervals
>>> merge = P.Interval(*intervals)
>>> merge
[1,6] | [8,10] | [15,18]
>>> # Output as a list of lists
>>> [[i.lower, i.upper] for i in merge]
[[1,6],[8,10],[15,18]]

文档可以在此处找到：https://github.com/AlexandreDecan/portion

（注：该文档与it技术有关，具体内容请参阅链接页面）
2
我们可以按照第一个区间进行排序，通过逐一检查每个区间而不是将其附加到另一个区间来在同一区间列表中构建合并列表。因此，我们对每个区间增加i，interval_index是当前正在检查的区间。
x =[[1,3],[2,6],[8,10],[15,18]]
#y  = [[1,3],[2,6],[8,10],[15,18],[19,25],[20,26],[25,30], [32,40]]

def merge_intervals(intervals):
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    interval_index = 0
    #print(sorted_intervals)
    for  i in sorted_intervals:

        if i[0] > sorted_intervals[interval_index][1]:
            interval_index += 1
            sorted_intervals[interval_index] = i
        else:
            sorted_intervals[interval_index] = [sorted_intervals[interval_index][0], i[1]]
    #print(sorted_intervals)
    return sorted_intervals[:interval_index+1]

print(merge_intervals(x)) #-->[[1, 6], [8, 10], [15, 18]]
#print ("------------------------------")
#print(merge_intervals(y)) #-->[[1, 6], [8, 10], [15, 18], [19, 30], [32, 40]]
1
刚刚看到了你的解决方案。你有检查过[[1,4],[2,3]]吗？我认为它会失败。如果我错了，请告诉我。 - Sachin Sharma
可以确认，如果一个时间间隔包含在另一个时间间隔内，这将失败。 - quadratecode
1
这篇文章已经很旧了，但如果有人偶然发现的话，我想加入我的两分意见，因为我对上面的答案并不完全满意。
我要先说一下我的解决方案，当我处理区间时，我更喜欢将它们转换为python3的范围（可能是你的Interval类的优雅替代品），因为我觉得他们很容易使用。但是，你需要记住，就像Python中的其他一切一样，范围是半开放的，所以停止坐标不在区间“内部”。对我的解决方案没有影响，但需要注意。
我的解决方案：
# Start by converting the intervals to ranges.
my_intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
my_ranges = [range(start, stop) for start, stop in my_intervals]


# Next, define a check which will return True if two ranges overlap.
# The double inequality approach means that your intervals don't
# need to be sorted to compare them.
def overlap(range1, range2):
    if range1.start <= range2.stop and range2.start <= range1.stop:
        return True
    return False


# Finally, the actual function that returns a list of merged ranges.
def merge_range_list(ranges):
    ranges_copy = sorted(ranges.copy(), key=lambda x: x.stop)
    ranges_copy = sorted(ranges_copy, key=lambda x: x.start)
    merged_ranges = []

    while ranges_copy:
        range1 = ranges_copy[0]
        del ranges_copy[0]

        merges = []  # This will store the position of ranges that get merged.

        for i, range2 in enumerate(ranges_copy):
            if overlap(range1, range2):  # Use our premade check function.
                range1 = range(min([range1.start, range2.start]),  # Overwrite with merged range.
                               max([range1.stop, range2.stop]))
                merges.append(i)

        merged_ranges.append(range1)

        # Time to delete the ranges that got merged so we don't use them again.
        # This needs to be done in reverse order so that the index doesn't move.
        for i in reversed(merges):
            del ranges_copy[i]

    return merged_ranges

print(merge_range_list(my_ranges))  # --> [range(1, 6), range(8, 10), range(15, 18)]
0
迟到了，但这是我的解决方案。通常我发现带有不变量的递归更容易概念化。在这种情况下，不变量是 head 始终被合并，而 tail 则始终等待合并，并将 head 的最后一个元素与 tail 的第一个元素进行比较。
应该使用带有 key 参数的 sorted 而不是使用列表推导式。
不确定使用切片和连接列表的效率如何。
def _merge(head, tail):
    if tail == []:
        return head

    a, b = head[-1]
    x, y = tail[0]

    do_merge = b > x
    if do_merge:
        head_ = head[:-1] + [(a, max(b, y))]
        tail_ = tail[1:]
        return _merge(head_, tail_)
    else:
        head_ = head + tail[:1]
        tail_ = tail[1:]
        return _merge(head_, tail_)


def merge_intervals(lst):
    if len(lst) <= 1:
        return lst
    lst = sorted(lst, key=lambda x: x[0])
    return _merge(lst[:1], lst[1:])
0

为每个端点创建一对：(value; kind = +/-1 表示区间的起始或结束)

按值进行排序。如果出现平局，选择带有 -1 的配对，如果您需要合并具有重叠结尾的区间，例如 0-1 和 1-2

创建 CurrCount = 0，遍历排序后的列表，将 kind 添加到 CurrCount 中。当 CurrCount 变为非零时开始新的结果区间，当 CurrCount 变为零时结束区间。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接