public int[][] insert(int[][] intervals, int[] newInterval) {
	if(intervals.length==0)
	{
		int val[][]= {{newInterval[0],newInterval[1]}};
		return val;
	}
	List<Integer>list=new ArrayList<Integer>();
	//二分找到位置
	int l=0,r=intervals.length-1;
	int index=0;
	while (l<r) {
		int mid=(l+r)/2;
		if(intervals[mid][0]==newInterval[0])
		{
			l=mid+1;r=mid-1;
		}
		else if(intervals[mid][0]<newInterval[0])
		{
			l=mid+1;
		}
		else {
			r=mid-1;
		}
	}
	index=l;
	int left=intervals[0][0],right=intervals[0][1];
	if(index==0) {
		left=newInterval[0];right=newInterval[1];
	}
	for(int i=0;i<index;i++)
	{
		if(intervals[i][0]<=right)
		 {
			 if(intervals[i][1]>right)
				 right=intervals[i][1];
		 }
		 else {
			list.add(left);
			list.add(right);
			left=intervals[i][0];
			right=intervals[i][1];
		}
	}
	if(newInterval[0]<=right)
	 {
		 if(newInterval[1]>right)
			 right=newInterval[1];
	 }
	 else {
		list.add(left);
		list.add(right);
		left=newInterval[0];
		right=newInterval[1];
	}
	for(int i=index;i<intervals.length;i++)
	{
		if(intervals[i][0]<=right)
		 {
			 if(intervals[i][1]>right)
				 right=intervals[i][1];
		 }
		 else {
			list.add(left);
			list.add(right);
			left=intervals[i][0];
			right=intervals[i][1];
		}
	}
	list.add(left);
	list.add(right);
	 int val[][]=new int [list.size()/2][2];
	 for(int i=0;i<list.size();i+=2)
	 {
		 val[i/2][0]=list.get(i);
		 val[i/2][1]=list.get(i+1);
	 }
	 return val;
   }