【每日一题Day308】LC57插入区间 | 模拟

简介: 【每日一题Day308】LC57插入区间 | 模拟

插入区间【LC57】

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

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

  • 思路
    首先根据起始端点找到插入区间的位置,在该位置前的所有区间可以直接插入;该位置后的区间,需要考虑插入新区间后是否发生了重叠,如果发生了重叠那么合并区间
  • 实现
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int n = intervals.length;
        // 先找到插入位置
        int i = -1;
        while (i + 1 < n && intervals[i + 1][0] < newInterval[0]){        
            i++;
            res.add(intervals[i]);
        }
        if (i == -1){
            res.add(newInterval);
            i++;
        }else {
            int[] pre = res.get(res.size() - 1);
            if (pre[1] >= newInterval[0]){// 有交叉
                pre[1] = Math.max(pre[1], newInterval[1]);
            }else{
                res.add(newInterval);
            }
        }
        for (; i < n; i++){
            int[] pre = res.get(res.size() - 1);
            if (pre[1] >= intervals[i][0]){// 有交叉
                pre[1] = Math.max(pre[1], intervals[i][1]);
            }else{
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

image.png

目录
相关文章
|
7月前
【每日一题Day258】LC2532过桥的时间 | 模拟 优先队列
【每日一题Day258】LC2532过桥的时间 | 模拟 优先队列
47 0
|
7月前
【每日一题Day345】LC2562找出数组的串联值 | 模拟
【每日一题Day345】LC2562找出数组的串联值 | 模拟
43 0
|
7月前
【每日一题Day290】LC1281整数的各位积和之差 | 模拟
【每日一题Day290】LC1281整数的各位积和之差 | 模拟
48 0
|
7月前
【每日一题Day268】LC415字符串相加 | 模拟
【每日一题Day268】LC415字符串相加 | 模拟
51 0
|
7月前
【每日一题Day155】LC1630等差子数组 | 枚举+排序
【每日一题Day155】LC1630等差子数组 | 枚举+排序
46 0
|
7月前
【每日一题Day191】LC2423删除字符使频率相同 | 枚举 分类讨论
【每日一题Day191】LC2423删除字符使频率相同 | 枚举 分类讨论
55 0
|
7月前
【每日一题Day278】LC2500删除每行中的最大值 | 排序+模拟
【每日一题Day278】LC2500删除每行中的最大值 | 排序+模拟
50 0
|
7月前
|
前端开发
【每日一题Day228】LC2460对数组执行操作 | 模拟+双指针
【每日一题Day228】LC2460对数组执行操作 | 模拟+双指针
44 0
|
7月前
|
存储
【每日一题Day307】LC56合并区间 | 排序
【每日一题Day307】LC56合并区间 | 排序
44 0
|
7月前
【每日一题Day138】LC1653使字符串平衡的最少删除次数 | 前后缀 动态规划
【每日一题Day138】LC1653使字符串平衡的最少删除次数 | 前后缀 动态规划
61 0