### Problem Statement

Given a list of non-overlapping intervals, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.

### Example:

```Input 1: intervals: [[1,3], [5,7], [8,12]], interval = [4,6]
Output 1: [[1,3], [4,7], [8,12]]
Explanation: After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7].

Input 2: intervals: [[1,3], [5,7], [8,12]], interval = [4,10]
Output 2: [[1,3], [4,12]]
Explanation: After insertion, since [4,10] overlaps with [5,7] & [8,12], we merged them into [4,12].```

### Code

```import java.util.*;

class InsertInterval {

public static List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if (intervals == null || intervals.isEmpty())
return Arrays.asList(newInterval);

List<Interval> mergedIntervals = new ArrayList<>();

int i = 0;
// skip (and add to output) all intervals that come before the 'newInterval'
while (i < intervals.size() && intervals.get(i).end < newInterval.start)

// merge all intervals that overlap with 'newInterval'
while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
i++;
}

// insert the newInterval

// add all the remaining intervals to the output
while (i < intervals.size())

return mergedIntervals;
}

public static void main(String[] args) {
List<Interval> input = new ArrayList<Interval>();
System.out.print("Intervals after inserting the new interval: ");
for (Interval interval : InsertInterval.insert(input, new Interval(4, 6)))
System.out.print("[" + interval.start + "," + interval.end + "] ");
System.out.println();

input = new ArrayList<Interval>();
System.out.print("Intervals after inserting the new interval: ");
for (Interval interval : InsertInterval.insert(input, new Interval(4, 10)))
System.out.print("[" + interval.start + "," + interval.end + "] ");
System.out.println();
}
}

class Interval {
int start;
int end;

public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}```
```using namespace std;

#include <iostream>
#include <vector>

class Interval {
public:
int start = 0;
int end = 0;

Interval(int start, int end) {
this->start = start;
this->end = end;
}
};

class InsertInterval {
public:
static vector<Interval> insert(const vector<Interval> &intervals, Interval newInterval) {
if (intervals.empty()) {
return vector<Interval>{newInterval};
}

vector<Interval> mergedIntervals;

int i = 0;
// skip (and add to output) all intervals that come before the 'newInterval'
while (i < intervals.size() && intervals[i].end < newInterval.start) {
mergedIntervals.push_back(intervals[i++]);
}

// merge all intervals that overlap with 'newInterval'
while (i < intervals.size() && intervals[i].start <= newInterval.end) {
newInterval.start = min(intervals[i].start, newInterval.start);
newInterval.end = max(intervals[i].end, newInterval.end);
i++;
}

// insert the newInterval
mergedIntervals.push_back(newInterval);

// add all the remaining intervals to the output
while (i < intervals.size()) {
mergedIntervals.push_back(intervals[i++]);
}

return mergedIntervals;
}
};

int main(int argc, char *argv[]) {
vector<Interval> input = {{1, 3}, {5, 7}, {8, 12}};
cout << "Intervals after inserting the new interval: ";
for (auto interval : InsertInterval::insert(input, {4, 6})) {
cout << "[" << interval.start << "," << interval.end << "] ";
}
cout << endl;

cout << "Intervals after inserting the new interval: ";
for (auto interval : InsertInterval::insert(input, {4, 10})) {
cout << "[" << interval.start << "," << interval.end << "] ";
}
cout << endl;

}```
```def insert(intervals, new_interval):
merged = []
i, start, end = 0, 0, 1

# skip (and add to output) all intervals that come before the 'new_interval'
while i < len(intervals) and intervals[i][end] < new_interval[start]:
merged.append(intervals[i])
i += 1

# merge all intervals that overlap with 'new_interval'
while i < len(intervals) and intervals[i][start] <= new_interval[end]:
new_interval[start] = min(intervals[i][start], new_interval[start])
new_interval[end] = max(intervals[i][end], new_interval[end])
i += 1

# insert the new_interval
merged.append(new_interval)

# add all the remaining intervals to the output
while i < len(intervals):
merged.append(intervals[i])
i += 1
return merged

def main():
print("Intervals after inserting the new interval: " + str(insert([[1, 3], [5, 7], [8, 12]], [4, 6])))
print("Intervals after inserting the new interval: " + str(insert([[1, 3], [5, 7], [8, 12]], [4, 10])))

main()```

### Output:

```Intervals after inserting the new interval: [1,3] [4,7] [8,12]
Intervals after inserting the new interval: [1,3] [4,12] ```

### Time and Space Complexity

Time Complexity: As we are traversing the complete list. So, Overall time complexity is O(nlogn).

Space Complexity: O(N), Since we are returning a new list of Intervals after inserting the new interval.