leetcode56-合并区间

原题

给出一个区间的集合,请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解法

思想

这道题和leetcode435-无重叠区间方法有一点类似,先排序,再处理区间。

代码

Java

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length<2) return intervals;
        Arrays.sort(intervals, (array1,array2)->{
            return array1[0]-array2[0];
        });
        int lastIndex = 0;
        int cur = 1;
        List<int[]> list = new ArrayList<>();
        while(cur < intervals.length){
            //如果两个区间没有重叠部分,都保留
            if(intervals[lastIndex][1]<intervals[cur][0]){
                list.add(intervals[lastIndex]);
                lastIndex = cur;
                cur++;
            //如果两个区间重叠,合并两个区间
            }else{
                intervals[lastIndex][1] = Math.max(intervals[lastIndex][1],intervals[cur][1]);
                cur++;
            }
        }
        list.add(intervals[lastIndex]);
        int[][] ans = new int[list.size()][2];
        for(int i = 0;i<list.size();i++){
            ans[i] = list.get(i);
        }
        return ans;
    }
}

Go(2020/07/05)

func merge(intervals [][]int) [][]int {
    if len(intervals) < 2 {return intervals}
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0]<intervals[j][0]
    })
    lastIndex := 0
    cur := 1
    var list [][]int
    for cur < len(intervals){
        if intervals[lastIndex][1]<intervals[cur][0]{
            list = append(list, intervals[lastIndex])
            lastIndex = cur
            cur++
        }else{
            intervals[lastIndex][1] = int(math.Max(float64(intervals[lastIndex][1]), float64(intervals[cur][1])))
            cur++
        }
    }
    list = append(list, intervals[lastIndex])
    return list
}

Python(2020/07/05)

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        if len(intervals) < 2: return intervals
        intervals = sorted(intervals, key=lambda e: e[0])
        lastIndex = 0
        cur = 1
        list = []
        while cur < len(intervals):
            if intervals[lastIndex][1] < intervals[cur][0]:
                list.append(intervals[lastIndex])
                lastIndex = cur
                cur += 1
            else:
                intervals[lastIndex][1] = max(intervals[lastIndex][1], intervals[cur][1])
                cur += 1
        list.append(intervals[lastIndex])
        return list

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode56-%e5%90%88%e5%b9%b6%e5%8c%ba%e9%97%b4/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月15日
下一篇 2020年4月16日

相关推荐

  • leetcode278-第一个错误的版本

    原题 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假…

    算法 2020年1月2日
    090
  • 程序员面试金典01.06-字符串压缩

    原题(来源Leetcode) 字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字…

    算法 2020年3月16日
    0230
  • 力扣杯春季个人赛-剧情触发时间

    这次的个人赛真是让我认清了自己的实力。。两道困难题都没做出?,虽然大家的通过率也不咋地。。 最后排名 我记录一道做出来的题吧,这道题是一道中等题,通过率如下,虽然题目不难,但由于时…

    2020年4月18日
    0430
  • leetcode289-生命游戏

    原题 根据 百度百科 ,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞…

    算法 2020年4月2日
    0300
  • leetcode191-位1的个数

    原题 编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。 示例 1: 输入: 000000000000000000000000…

    算法 2020年4月15日
    0120
  • leetcode20-有效的括号

    原题 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序…

    算法 2019年12月11日
    0210
  • leetcode206-反转链表

    原题 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法…

    2019年12月16日
    0160
  • leetcode560-和为K的子数组

    原题 给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 , [1,1]…

    算法 2020年5月15日
    0470
  • leetcode1431-拥有最多糖果的孩子(儿童节快乐!)

    原题 给你一个数组 candies 和一个整数 extraCandies ,其中 candies[i] 代表第 i 个孩子拥有的糖果数目。 对每一个孩子,检查是否存在一种方案,将额…

    算法 2020年6月1日
    0310
  • 剑指offer57-和为s的连续正数序列

    原题(来源Leetcode) 输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。 序列内的数字由小到大排列,不同序列按照首个数字从小到…

    算法 2020年3月6日
    050

发表回复

登录后才能评论