【python-leetcode56-区间合并】合并区间
问题描述: 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输入: [[1,4],[4,5]] 这题之间看过,今天又看到了,大致知道是先要排序,但是忘了怎么更新结果。 核心:其实是贪心法的体现,关注于相邻的两个数组,那么就有两种情况,以[[1,18]]为例。 先对二维数组按一维数组的第0位进行排序,假设结果是res=[]。 当res为空时先将[1,3]加入到res中,再遍历到[2,6],此时有两种情况,如果当前数组的第0位大于res中最后一个数组的第1位,说明当前数组和res末尾的数组不会重叠,此时之间将当前数组加到res末尾。如果当前数组第0位小于或等于res末尾数组第1位,再判断当前数组第1位和res末尾数组第一位誰大,将其更新res末尾数组的第一位。依次类推。 代码: class Solution: def merge(self,intervals: List[List[int]]) -> List[List[int]]: res = [] intervals.sort() for i in intervals: if not res or res[-1][1]<i[0]: res.append(i) else: res[-1] = max(res[-1],i[1]) return res 结果: (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |