插入区间
题目形容：给你一个 无重叠的 ，依照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你须要确保列表中的区间依然有序且不重叠（如果有必要的话，能够合并区间）。
示例阐明请见LeetCode官网。
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
解法一：遍历数组
- 首先如果intervals为空，因为不须要解决合并，所以间接返回一个区间newInterval；
如果intervals不为空，申明1个变量length记录intervals的区间数，而后分以下几种状况进行解决：
- 如果新区间newInterval的最大值小于intervals所有区间的最小值，则不须要合并，将新区间放在intervals的最后面，而后返回；
- 如果新区间newInterval的最小值大于intervals所有区间的最大值，则不须要合并，将新区间放在intervals的最初面，而后返回；
如果后面两种状况不存在，则用matchFirst和matchSecond记录newInterval的2个数，newLength为新区间的数量初始为length+1，用一个boolean数组flag记录intervals有哪些区间被合并，而后遍历intervals的所有区间：
- curFirst和curSecond为以后区间的2个数，用matchFirst、matchSecond、curFirst、curSecond判断2个区间是否相交，如果相交，则更新matchFirst和matchSecond的值，并且将以后区间的标识更新为已合并。
- 遍历实现后，初始化一个新的区间数组newIntervals，将新区间
{matchFirst, matchSecond}和intervals放入newIntervals中没有被合并的区间放入newIntervals中（须要判断将新区间放在适合的地位），而后返回newIntervals。
public class LeetCode_057 { public static int[][] insert(int[][] intervals, int[] newInterval) { if (intervals == null || intervals.length == 0) { return new int[][]{newInterval}; } int length = intervals.length; if (newInterval[1] < intervals[0][0]) { // 如果新区间的最大值小于所有区间的最小值，则不须要合并，将新区间放在intervals的最后面 int[][] newIntervals = new int[length + 1][2]; newIntervals[0] = newInterval; for (int i = 0; i < length; i++) { newIntervals[i + 1] = intervals[i]; } return newIntervals; } else if (newInterval[0] > intervals[length - 1][1]) { // 如果新区间的最小值大于所有区间的最大值，则不须要合并，将新区间放在intervals的最初面 int[][] newIntervals = new int[length + 1][2]; for (int i = 0; i < length; i++) { newIntervals[i] = intervals[i]; } newIntervals[length] = newInterval; return newIntervals; } else { int matchFirst = newInterval[0], matchSecond = newInterval[1], newLength = length + 1; boolean[] flag = new boolean[length]; for (int i = 0; i < length; i++) { int curFirst = intervals[i][0], curSecond = intervals[i][1]; if (((matchFirst >= curFirst && matchFirst <= curSecond) || (matchSecond >= curFirst && matchSecond <= curSecond)) || ((curFirst >= matchFirst && curFirst <= matchSecond) || (curSecond >= matchFirst && curSecond <= matchSecond))) { // 有交加 matchFirst = Math.min(matchFirst, curFirst); matchSecond = Math.max(matchSecond, curSecond); flag[i] = true; newLength--; } } int[][] newIntervals = new int[newLength][2]; boolean added = false; int pos = 0; for (int i = 0; i < length; i++) { if (!flag[i]) { if (added) { newIntervals[pos++] = intervals[i]; } else { if (matchSecond < intervals[i][0]) { newIntervals[pos++] = new int[]{matchFirst, matchSecond}; added = true; } newIntervals[pos++] = intervals[i]; } } } if (!added) { newIntervals[pos++] = new int[]{matchFirst, matchSecond}; } return newIntervals; } } public static void main(String[] args) { int[][] intervals = new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}; int[] newInterval = new int[]{4, 8}; for (int[] ints : insert(intervals, newInterval)) { for (int anInt : ints) { System.out.print(anInt + " "); } System.out.println(); } }}【每日寄语】 明天也是值得你用可恶和温顺去看待的一天呀。