网站建设要多久,如何制作网站首页,东莞外贸推广公司,wordpress可不可以做论坛我们可以将区间按照左端点升序排列#xff0c;然后遍历区间进行合并操作。
我们先将第一个区间加入答案#xff0c;然后依次考虑之后的每个区间#xff1a;
如果答案数组中最后一个区间的右端点小于当前考虑区间的左端点#xff0c;说明两个区间不会重合#xff0c;因此…
我们可以将区间按照左端点升序排列然后遍历区间进行合并操作。
我们先将第一个区间加入答案然后依次考虑之后的每个区间
如果答案数组中最后一个区间的右端点小于当前考虑区间的左端点说明两个区间不会重合因此我们可以直接将当前区间加入答案数组末尾否则说明两个区间重合我们需要用当前区间的右端点更新答案数组中最后一个区间的右端点将其置为二者的较大值。
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) - a[0] - b[0]);Listint[] 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[0] 此时如果新区间还没有被加入那么将新区间加入到答案中然后将当前区间加入到答案中。当前区间在新区间的左侧即 a[1]newInterval[0]此时将当前区间加入到答案中。否则说明当前区间与新区间有交集我们取当前区间的左端点和新区间的左端点的最小值以及当前区间的右端点和新区间的右端点的最大值作为新区间的左右端点然后继续遍历区间列表。
遍历结束如果新区间还没有被加入那么将新区间加入到答案中。
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {ArrayListint[] ints new ArrayList();//记录要合并数组的头区间int start newInterval[0];//记录要合并数组的尾区间int end newInterval[1];//要插入区间是否已经插入boolean b false;for(int[] a :intervals) {//要插入的区间右端点小于当前区间的左端点if (enda[0]){//如果要插入的区间还没有插入的话就说明此时要插入的区间可以插入了不和后面区间合并了。if (!b){ints.add(new int[]{start,end});b true;}//将不需要合并区间插入ints.add(a);//要插入区间左端点大于此时区间的右端点说明不重合可以插入了}else if (a[1]start){ints.add(a);}else {//此时肯定是重合了则左端点选出最小的右端点选出最大的。start Math.min(start,a[0]);end Math.max(end,a[1]);}}//如果遍历完了还没有插入的话直接再最后插入。if (!b){ints.add(new int[]{start,end});}return ints.toArray(new int[ints.size()][]);}
}
