# Insert Interval

Given a set of _non-overlapping _intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

``````Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]``````

Example 2:

``````Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].``````

## Solution

(13ms, 64%)

``````/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> ans = new ArrayList<>();

int index = 0;
while (index < intervals.size()) {
if (newInterval.start > intervals.get(index).start) {
index++;
} else {
break;
}
}

Interval last = null;
for (Interval interval : intervals) {
if (last == null || interval.start > last.end) {