力扣区间题：合并区间、插入区间

我们可以将区间按照左端点升序排列，然后遍历区间进行合并操作。

我们先将第一个区间加入答案，然后依次考虑之后的每个区间：

• 如果答案数组中最后一个区间的右端点小于当前考虑区间的左端点，说明两个区间不会重合，因此我们可以直接将当前区间加入答案数组末尾；
• 否则，说明两个区间重合，我们需要用当前区间的右端点更新答案数组中最后一个区间的右端点，将其置为二者的较大值。

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List ans = new ArrayList();ans.add(intervals[0]);for (int i = 1; i < intervals.length; ++i) {int s = intervals[i][0], e = intervals[i][1];if (ans.get(ans.size() - 1)[1] < s) {ans.add(intervals[i]);} else {ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], e);}}return ans.toArray(new int[ans.size()][]);}}

这个有两种解法，一种就是直接将这个要插入的区间加入数组，让合并区间的算法走一遍，就可以了。

第二种算法：

我们可以遍历区间列表 intervalsintervalsintervals，记当前区间为 a，对于每个区间有三种情况：

• 当前区间在新区间的右侧，即 newInterval[1]
• 当前区间在新区间的左侧，即 a[1]<newInterval[0]，此时将当前区间加入到答案中。
• 否则，说明当前区间与新区间有交集，我们取当前区间的左端点和新区间的左端点的最小值，以及当前区间的右端点和新区间的右端点的最大值，作为新区间的左右端点，然后继续遍历区间列表。

遍历结束，如果新区间还没有被加入，那么将新区间加入到答案中。

class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {ArrayList ints = new ArrayList();//记录要合并数组的头区间int start= newInterval[0];//记录要合并数组的尾区间int end = newInterval[1];//要插入区间是否已经插入boolean b = false;for(int[] a :intervals) {//要插入的区间右端点小于当前区间的左端点 if (end