Leetcode之插入区间

问题描述：

给出一个无重叠的 ，按照区间起始端点排序的区间列表。 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠(如果有必要的话，可以合并区间)。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5] 输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出：[[1,2],[3,10],[12,16]] 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

问题解法：

法一：排序+合并

因为在之前已经写过合并区间的方法了。所以可以得到一个新区间再排序。

class Solution { public int[][] merge(int[][] intervals) { if(intervals==null) return null; boolean[] flags=new boolean[intervals.length]; int num=0; for(int i=0;i<intervals.length;i++) { //排序 for(int j=i+1;j<intervals.length;j++) { if(intervals[j][0]<intervals[i][0]) { //交换 int temp1=intervals[j][0]; int temp2=intervals[j][1]; intervals[j][0]=intervals[i][0]; intervals[j][1]=intervals[i][1]; intervals[i][0]=temp1; intervals[i][1]=temp2; } } if(i!=0) { if(intervals[i][0]<=intervals[i-1][1]) { intervals[i][0]=intervals[i-1][0];//合并成一个区间 intervals[i][1]=Math.max(intervals[i-1][1], intervals[i][1]); flags[i-1]=false; num--; } } flags[i]=true; num++; } int[][] re=new int[num][2]; for(int i=0,j=0;i<flags.length;i++) { if(flags[i]) re[j++]=intervals[i]; } return re; } public int[][] insert(int[][] intervals, int[] newInterval) { int[][] re=new int[intervals.length+1][2]; for(int i=0;i<intervals.length;i++) { re[i][0]=intervals[i][0]; re[i][1]=intervals[i][1]; } re[re.length-1][0]=newInterval[0]; re[re.length-1][1]=newInterval[1]; return merge(re); } }

法二：二分查找+合并

上面的排序方法我们选择的是冒泡排序(合并区间题目的算法)。这道题目给的是有序的区间集合。因此我们可以对区间集合进行二分查找。将排序问题变为二分查找。再进行合并。

class Solution { public int[][] getRe(int[][]intervals, int[] newInterval){ if(intervals==null||intervals.length==0) { int[][] re=new int[1][2]; re[0][0]=newInterval[0]; re[0][1]=newInterval[1]; return re; } int[][] re=new int[intervals.length+1][2]; int start=0,end=intervals.length; //注意这里end是len不是len-1 int mid=(start+end)/2; while(start<end) { mid=(start+end)/2; if(newInterval[0]>intervals[mid][0]) { if(start!=mid) start=mid; else break; }else if(newInterval[0]==intervals[mid][0]) { break; }else { if(end!=mid) end=mid; else break; } } for(int i=0;i<intervals.length;i++) { if(i<mid) { re[i][0]=intervals[i][0]; re[i][1]=intervals[i][1]; } else if(i==mid) { if(start==end&&newInterval[0]<intervals[i][0]) { re[i][0]=newInterval[0]; re[i][1]=newInterval[1]; re[i+1][0]=intervals[i][0]; re[i+1][1]=intervals[i][1]; }else { re[i][0]=intervals[i][0]; re[i][1]=intervals[i][1]; re[i+1][0]=newInterval[0]; re[i+1][1]=newInterval[1]; } }else { re[i+1][0]=intervals[i][0]; re[i+1][1]=intervals[i][1]; } } return re; } public int[][] merge(int[][] intervals) { if(intervals==null) return null; boolean[] flags=new boolean[intervals.length]; int num=0; for(int i=0;i<intervals.length;i++) { if(i!=0) { if(intervals[i][0]<=intervals[i-1][1]) { intervals[i][0]=intervals[i-1][0];//合并成一个区间 intervals[i][1]=Math.max(intervals[i-1][1], intervals[i][1]); flags[i-1]=false; num--; } } flags[i]=true; num++; } int[][] re=new int[num][2]; for(int i=0,j=0;i<flags.length;i++) { if(flags[i]) re[j++]=intervals[i]; } return re; } public int[][] insert(int[][] intervals, int[] newInterval) { int[][] re=getRe(intervals,newInterval); return merge(re); } }

法三：贪心

贪心算法。我们将整个区间集合分为三部分————在newInterval[0]之前的区间需要全加进去。然后是newInterval区间与最后一个区间合并(如果需要的话)。再将之后的每一个区间添加进来，需要合并的进行合并。

class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { if(intervals==null||intervals.length==0) { int[][] re=new int[1][2]; re[0][0]=newInterval[0]; re[0][1]=newInterval[1]; return re; } ArrayList<int[]>lists=new ArrayList<int[]>(); int flag=-1; for(int i=0;i<intervals.length;i++) { if(intervals[i][0]<newInterval[0]) { if(intervals[i][1]<newInterval[0]) {//添加i int[]b=new int[2]; b[0]=intervals[i][0]; b[1]=intervals[i][1]; flag=i+1; lists.add(b); } else { int[]b=new int[2]; b[0]=intervals[i][0]; b[1]=Math.max(intervals[i][1], newInterval[1]); lists.add(b); flag=i+1; break; } }else { flag=i; break; } } ///添加newInterval if(lists.size()==0) { int[]b=new int[2]; b[0]=newInterval[0]; b[1]=newInterval[1]; lists.add(b); }else { int[] t=lists.get(lists.size()-1); if(t[1]<newInterval[0]) {//不用合并 int[]b=new int[2]; b[0]=newInterval[0]; b[1]=newInterval[1]; lists.add(b); }else { t[1]=Math.max(intervals[flag-1][1], newInterval[1]); } } for(int i=flag;i<intervals.length;i++) { int[] a=lists.get(lists.size()-1); if(a[1]>=intervals[i][0]) { if(a[1]<=intervals[i][1]) { a[1]=intervals[i][1]; for(int j=i+1;j<intervals.length;j++) { int[]b=new int[2]; b[0]=intervals[j][0]; b[1]=intervals[j][1]; lists.add(b); } break; } }else { int[]b=new int[2]; b[0]=intervals[i][0]; b[1]=intervals[i][1]; lists.add(b); } } return (int[][]) lists.toArray(new int[lists.size()][2]); } }

总结知识点

二分法的端点贪心算法arraylist转为二维数组的写法((int[][])lists.toArray(new int[lists.size()][2]))： toArray()调用的时候一般要传一个数组指定类型，如果不传参数会默认返回Object数组，然后toArray内部会自动判断传入数组大小是否小于list中元素的个数，如果小于则会产生一个大小等于元素个数的新数组，写入数据后返回，否则写入传入的数组，然后返回。