【每日一题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

目录
打赏
0
0
0
0
5
分享
相关文章
|
9月前
【每日一题Day278】LC2500删除每行中的最大值 | 排序+模拟
【每日一题Day278】LC2500删除每行中的最大值 | 排序+模拟
58 0
【每日一题Day103】LC1669合并两个链表 | 模拟
思路:遍历链表找到list1中的第a−1个节点和第b+1个节点,然后将第a−1个节点指向list2链表的初始节点,list2链表的尾节点指向list1中的第b+1个节点
99 0
【每日一题Day103】LC1669合并两个链表 | 模拟
|
9月前
【每日一题Day345】LC2562找出数组的串联值 | 模拟
【每日一题Day345】LC2562找出数组的串联值 | 模拟
49 0
【每日一题DAY24】LC1704判断字符串的两半是否相似|双指针 模拟
两个字符串 相似 的前提是它们都含有相同数目的元音('a','e','i','o','u','A','E','I','O','U')。注意,s 可能同时含有大写和小写字母。
85 0
|
9月前
|
【每日一题Day228】LC2460对数组执行操作 | 模拟+双指针
【每日一题Day228】LC2460对数组执行操作 | 模拟+双指针
50 0
【每日一题Day82】LC1806还原排列的最少操作步数 | 模拟
思路:按照题意进行变换,直至数组变为原始数组,记录变换次数
83 0
|
9月前
【每日一题Day258】LC2532过桥的时间 | 模拟 优先队列
【每日一题Day258】LC2532过桥的时间 | 模拟 优先队列
58 0
【每日一题Day108】LC1798你能构造出连续值的最大数目 | 贪心
局部最优:每次从数组中找到未选择数字中的最小值来更新区间,如果当前连续值x小于选择的数值coin,那么无法获得更大的区间,退出循环
62 0
|
9月前
【每日一题Day191】LC2423删除字符使频率相同 | 枚举 分类讨论
【每日一题Day191】LC2423删除字符使频率相同 | 枚举 分类讨论
62 0
|
9月前
|
【每日一题Day297】LC2682找出转圈游戏输家 | 模拟+哈希表
【每日一题Day297】LC2682找出转圈游戏输家 | 模拟+哈希表
79 0