# Insert Interval

## Problem

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

## Example

Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].

Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].

## Code - Java

/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
*   this.start = start;
*   this.end = end;
* }
*/

class Solution {
/**
* Insert newInterval into intervals.
*
* @param intervals:   Sorted interval list.
* @param newInterval: A new interval.
* @return: A new sorted interval list.
*/
public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
int size = intervals.size();

ArrayList<Interval> result = new ArrayList<>();
boolean inserted = false;

int i = 0;
int j = -1;
while (i < size || inserted == false) {

Interval candidate = null;
if (i == size || (inserted == false && intervals.get(i).start > newInterval.start)) {
candidate = newInterval;
inserted = true;
} else {
candidate = intervals.get(i);
i++;
}

if (j == -1) {
j++;
} else {
Interval prev = result.get(j);
if (prev.end >= candidate.start) {
prev.end = Math.max(candidate.end, prev.end);
} else {
}