57. Insert Interval

• Process the element of original interval list one by one
• If end of current element is less than start of newInterval, just add it to newList;
• If current element overlap with newInterval, merge it with newInterval and update newInterval with merged interval
• Since the original list is ordered, if start current element is large than end of newInterval, then the rest elements don't overlap with newInterval. We can add them to newList.

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    List<Interval> resultList = new ArrayList<Interval>();
    if( intervals.size() == 0 ) {
        resultList.add(newInterval);
        return resultList;
    }
    int index = 0;
    while( index < intervals.size() && intervals.get(index).end < newInterval.start )
        resultList.add(intervals.get(index++));
    while( index < intervals.size() && isInter(intervals.get(index), newInterval) ) {
        newInterval.start = Math.min(intervals.get(index).start, newInterval.start);
        newInterval.end = Math.max(intervals.get(index).end, newInterval.end);
        index++;
    }
    resultList.add(newInterval);
    for(int i = index; i < intervals.size(); i++)
        resultList.add(intervals.get(i));
    return resultList;
}

public boolean isInter(Interval first, Interval second) {
    return !(first.start > second.end || second.start > first.end);
}