heap的使用——合并K个排序间隔列表,和merge K个有序数组是一样的
2023-09-14 09:11:49 时间
577. 合并K个排序间隔列表
中文
English
将K个排序的间隔列表合并到一个排序的间隔列表中,你需要合并重叠的间隔。
样例
样例1
输入: [
[(1,3),(4,7),(6,8)],
[(1,2),(9,10)]
]
输出: [(1,3),(4,8),(9,10)]
样例2
输入: [
[(1,2),(5,6)],
[(3,4),(7,8)]
]
输出: [(1,2),(3,4),(5,6),(7,8)]
""" Definition of Interval. class Interval(object): def __init__(self, start, end): self.start = start self.end = end """ import heapq class Solution: """ @param intervals: the given k sorted interval lists @return: the new sorted interval list """ def mergeKSortedIntervalLists(self, intervals): # write your code here def append(arr, l, r): if not arr: arr.append(Interval(l, r)) return if arr[-1].start <= l <= arr[-1].end: arr[-1].end = max(r, arr[-1].end) else: arr.append(Interval(l, r)) q = [] for i,arr in enumerate(intervals): if arr: heapq.heappush(q, (intervals[i][0].start, intervals[i][0].end, i, 0)) ans = [] while q: l, r, i, j = heapq.heappop(q) append(ans, l, r) if j+1 < len(intervals[i]): heapq.heappush(q, (intervals[i][j+1].start, intervals[i][j+1].end, i, j+1)) return ans
相关文章
- hashmap和hashtable数组扩容_散列表扩容
- java打印数组元素_java Arrays快速打印数组的数据元素列表案例
- uni-app+php+workman实现简单聊天功能之交互实现(会话列表)
- 致远seeyon-OA系统脆弱性列表
- 经验分享 | 利用xpath爬取edu漏洞列表
- 【HTML】HTML 列表 ( 无序列表 | 有序列表 | 自定义列表 )
- 阿里二面:说一下Hashmap散列表的三大问题与线程安全问题
- Python-声明数组(列表)
- css通用全局样式~a链接、列表项、浮动各种样式
- MySQL列表查询实践深度探索C语言实现(c mysql 列表查询)
- javascript级联下拉列表实例代码(自写)
- js对列表中第一个值处理与jsp页面对列表中第一个值处理的区别详解
- Python列表list数组array用法实例解析
- jquerybind(click)传参让列表中每行绑定一个事件