leetcode57-插入区间

原题

给出一个无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

示例 1:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]]

示例 2:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出: [[1,2],[3,10],[12,16]] 解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

解法

思想

直接扫描,找到在哪里插入新区间(或融合区间)。

代码

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ans = new ArrayList<>();
        int cur = 0;
        boolean hasMerged = false;
        while(cur<intervals.length){
            if(!hasMerged && newInterval[0]<=intervals[cur][1]){
                if(newInterval[1]<intervals[cur][0]){
                    ans.add(newInterval);
                    ans.add(intervals[cur]);
                }
                else{
                    int start = Math.min(newInterval[0],intervals[cur][0]);
                    while(cur<intervals.length&&newInterval[1]>=intervals[cur][0]){
                        cur++;
                    }
                    cur--;
                    ans.add(new int[]{start,Math.max(newInterval[1],intervals[cur][1])});
                }
                hasMerged = true;
            }else ans.add(intervals[cur]);
            cur++;
        }
        if(!hasMerged) ans.add(newInterval);
        int[][] ansArray = new int[ans.size()][2];
        for(int i = 0;i<ans.size();i++){
            ansArray[i] = ans.get(i);
        }
        return ansArray;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode57-%e6%8f%92%e5%85%a5%e5%8c%ba%e9%97%b4/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月12日
下一篇 2020年5月13日

相关推荐

  • leetcode1300-转变数组后最接近目标值的数组和

    原题 给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 targe…

    算法 2020年6月14日
    0970
  • leetcode103-二叉树的锯齿形层次遍历

    原题 给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 例如:给定二叉树: [3,9,20,null,nul…

    算法 2020年1月25日
    060
  • leetcode210-课程表II

    原题 现在你总共有 n 门课需要选,记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0…

    算法 2020年5月17日
    0130
  • leetcode394-字符串解码

    原题 给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意…

    算法 2019年12月13日
    090
  • leetcode704-二分查找

    原题 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示…

    算法 2019年12月29日
    080
  • leetcode983-最低票价

    原题 在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车…

    算法 2020年5月6日
    0120
  • leetcode392-判断子序列

    原题 https://leetcode.cn/problems/is-subsequence/description 解法 最简单的双指针略。 对于进阶场景:如果有大量输入的 S,…

    算法 2024年3月24日
    040
  • leetcode73-矩阵置零

    原题 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [   [1,1,1],  …

    算法 2020年5月14日
    0100
  • leetcode297-二叉树的序列化与反序列化

    原题 序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。…

    算法 2020年1月15日
    0120
  • leetcode572-另一个树的子树

    原题 给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树…

    算法 2020年5月8日
    0380

发表回复

登录后才能评论