https://leetcode-cn.com/problems/merge-intervals/
# -*- coding:utf-8 -*- class Solution(object): def merge(self, intervals): """ :type intervals: List[List[int]] :rtype: List[List[int]] """ def cmp(x, y): if x[0] > y[0]: return 1 elif x[0] < y[0]: return -1 else: return 0 if len(intervals) == 1: return intervals import functools intervals = sorted(intervals, key=functools.cmp_to_key(cmp)) do_length = 0 do_idx = 1 max_length = len(intervals) while do_length < max_length - 1: if intervals[do_idx][0] <= intervals[do_idx - 1][1]: intervals[do_idx - 1][1] = max(intervals[do_idx][1], intervals[do_idx - 1][1]) intervals.remove(intervals[do_idx]) else: do_idx += 1 do_length += 1 return intervals if __name__ == '__main__': intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] intervals = [[1, 3], [5, 6]] # intervals = [[1, 4], [0, 2], [3, 5]] print(Solution().merge(intervals))
思路:首先是排序,然后根据当前的0号位是否小于前一个的1号位来判断这两个是否可以合并,如果可以就合并。
这里了解了python的自定义比较函数,还必须导入一个funtools。。学到了学到了。
插入区间只要在上面代码上做一些微小的改动,将newInterval插入intervals然后改一下边界条件即可。
# -*- coding:utf-8 -*- class Solution(object): def insert(self, intervals, newInterval): """ :type intervals: List[List[int]] :type newInterval: List[int] :rtype: List[List[int]] """ def cmp(x, y): if x[0] > y[0]: return 1 elif x[0] < y[0]: return -1 else: return 0 if len(intervals) == 0: return [newInterval] import functools intervals.append(newInterval) intervals = sorted(intervals, key=functools.cmp_to_key(cmp)) do_length = 0 do_idx = 1 max_length = len(intervals) while do_length < max_length - 1: if intervals[do_idx][0] <= intervals[do_idx - 1][1]: intervals[do_idx - 1][1] = max(intervals[do_idx][1], intervals[do_idx - 1][1]) intervals.remove(intervals[do_idx]) else: do_idx += 1 do_length += 1 return intervals if __name__ == '__main__': intervals = [] newInterval = [5, 7] print(Solution().insert(intervals, newInterval))
0 条评论