问题描述：
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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中元素的个数，如果小于则会产生一个大小等于元素个数的新数组，写入数据后返回，否则写入传入的数组，然后返回。