插入区间【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()][]); } }
