# 插入间隔Leetcode解决方案

## 使用案列

intervals = [[1,3],[6,9]], newInterval = [2,5]
[[1,5],[6,9]]

intervals = [], newInterval = [0,5]
[0,5]

## 代码

### 插入间隔Leetcode解决方案的C ++代码

#include <bits/stdc++.h>
using namespace std;

bool overlap(vector<int> a, vector<int> b){
return (a[0] <= b[0] && b[0] <= a[1]) || (b[0] <= a[0] && a[0] <= b[1]);
}

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int i;
vector<vector<int>> newIntervals;
for(i=0;i<intervals.size();i++)
if(overlap(intervals[i], newInterval))
break;
else
newIntervals.push_back(intervals[i]);
if(i<intervals.size()){
intervals[i][0] = min(intervals[i][0], newInterval[0]);
intervals[i][1] = max(intervals[i][1], newInterval[1]);
newIntervals.push_back(intervals[i]);
int j = i;
i++;
for(;i<intervals.size();i++)
if(overlap(intervals[j], intervals[i])){
newIntervals[j][0] = min(newIntervals[j][0], intervals[i][0]);
newIntervals[j][1] = max(newIntervals[j][1], intervals[i][1]);
} else
newIntervals.push_back(intervals[i]);
return newIntervals;
}
for(i=0;i<intervals.size();i++)
if(newIntervals[i][0]>newInterval[0])
break;
newIntervals.insert(newIntervals.begin() + i, newInterval);
return newIntervals;
}

int main(){
vector<vector<int>> intervals = {{0,5}};
vector<int> newInterval = {1,6};
vector<vector<int>> output = insert(intervals, newInterval);
for(int i=0;i<output.size();i++)
cout<<output[i][0]<<" "<<output[i][1];
}
0 6

### 用于插入间隔Leetcode解决方案的Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {

private static boolean overlap(int[] a, int[] b){
return (a[0] <= b[0] && b[0] <= a[1]) || (b[0] <= a[0] && a[0] <= b[1]);
}

private static int[][] insert(int[][] intervals, int[] newInterval) {
int i;
ArrayList<Integer[]> newIntervals = new ArrayList<Integer[]>();
for(i=0;i<intervals.length;i++)
if(overlap(intervals[i], newInterval))
break;
else
if(i<intervals.length){
intervals[i][0] = Math.min(intervals[i][0], newInterval[0]);
intervals[i][1] = Math.max(intervals[i][1], newInterval[1]);
int j = i;
i++;
for(;i<intervals.length;i++)
if(overlap(intervals[j], intervals[i])){
int a = Math.min(intervals[j][0], intervals[i][0]);
int b = Math.max(intervals[j][1], intervals[i][1]);
newIntervals.set(j, new Integer[]{a, b});
} else
int[][] to_return = new int[newIntervals.size()][2];
for(i=0;i<to_return.length;i++){
to_return[i][0] = newIntervals.get(i)[0];
to_return[i][1] = newIntervals.get(i)[1];
}
}
for(i=0;i<intervals.length;i++)
if(newIntervals.get(i)[0]>newInterval[0])
break;

newIntervals.add(i, new Integer[]{newInterval[0], newInterval[1]});

int[][] to_return = new int[newIntervals.size()][2];
for(i=0;i<to_return.length;i++){
to_return[i][0] = newIntervals.get(i)[0];
to_return[i][1] = newIntervals.get(i)[1];
}
}

public static void main (String[] args) throws java.lang.Exception {
int[][] intervals = {{0,5}};
int[] newInterval = {1,6};
int[][] output = insert(intervals, newInterval);
for(int i=0;i<intervals.length;i++)
System.out.print(output[i][0] + " " + output[i][1]);
}
}
0 6

## 复杂度分析

### 时间复杂度

BST节点之间的最小距离Leetcode解决方案