|
| 1 | +```text |
| 2 | +题目: 给出一个无重叠的,按照区间起始端点排序的区间列表 |
| 3 | + 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠 |
| 4 | + (如果有必要的话,可以合并区间) |
| 5 | + 示例1: |
| 6 | + 输入:intervals = [[1,3],[6,9]], newInterval = [2,5] |
| 7 | + 输出:[[1,5],[6,9]] |
| 8 | + 示例2: |
| 9 | + 输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] |
| 10 | + 输出:[[1,2],[3,10],[12,16]] |
| 11 | + 解释:这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10]重叠 |
| 12 | +1.贪心算法: |
| 13 | + [1]思路: |
| 14 | + (1)首先创建一个存放结果的二维数组,遍历给定的二维数组, |
| 15 | + 如果遍历到的数组第一个元素小于目标二维数组第一个元素则插入结果中; |
| 16 | + (2)不满足则跳出循环,将目标二维数组合并到结果中; |
| 17 | + (3)继续遍历插入剩余的数组到结果中(此时需要判断是否需要合并); |
| 18 | + [2]实现: |
| 19 | + class Solution { |
| 20 | + public int[][] insert(int[][] intervals, int[] newInterval) { |
| 21 | + // index表示遍历到的二维数组的下标 |
| 22 | + int index = 0, n = intervals.length; |
| 23 | + int newStart = newInterval[0], newEnd = newInterval[1]; |
| 24 | + // 创建结果对象 |
| 25 | + LinkedList<int[]> result = new LinkedList<>(); |
| 26 | + // 开始遍历给定二维数组 |
| 27 | + while (index < n && newStart > intervals[index][0]) { |
| 28 | + result.add(intervals[index++]); |
| 29 | + } |
| 30 | + // 若二维数组未完全遍历,则说明目标数组需要合并到给定的二维数组中 |
| 31 | + // 如果结果为空,则需要将目标数组直接插入结果;否则需要合并 |
| 32 | + // 若二维数组遍历完了,则说明目标数组的第一个元素比二维数组最后数组的第一个元素大 |
| 33 | + // 如果结果中最后一个数组的第二个元素小于目标数组的第一个元素,则直接插入;否则需要合并 |
| 34 | + if(result.isEmpty() || result.getLast()[1]<newStart){ |
| 35 | + result.add(newInterval); |
| 36 | + }else { |
| 37 | + int[] temp = result.removeLast(); |
| 38 | + temp[1] = Math.max(temp[1],newEnd); |
| 39 | + result.add(temp); |
| 40 | + } |
| 41 | + // 继续遍历 |
| 42 | + while (index < n){ |
| 43 | + int[] interval = intervals[index++]; |
| 44 | + int[] last = result.getLast(); |
| 45 | + // 每遍历到一个,需要与结果中的前一个作判断,若不存在重合,则直接插入,否则需合并 |
| 46 | + if(last[1] < interval[0]){ |
| 47 | + result.add(interval); |
| 48 | + }else { |
| 49 | + int[] temp = result.removeLast(); |
| 50 | + temp[1] = Math.max(temp[1],interval[1]); |
| 51 | + result.add(temp); |
| 52 | + } |
| 53 | + } |
| 54 | + return result.toArray(new int[result.size()][2]); |
| 55 | + } |
| 56 | + } |
| 57 | + [3]复杂度分析: |
| 58 | + (1)时间复杂度: O(n) |
| 59 | + (2)空间复杂度: O(n) |
| 60 | +``` |
0 commit comments