Insert Interval

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).

Have you met this question in a real interview? 

Yes

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]].

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) {

        ArrayList<Interval> result = new ArrayList<Interval>();

       

        // write your code here

        for(Interval interval : intervals){

            if(interval.end < newInterval.start){

                result.add(interval);

            } else if(interval.start > newInterval.end){

                result.add(newInterval);

                newInterval = interval;

            } else if(interval.end >= newInterval.start || interval.start <= newInterval.end){

                newInterval.start = Math.min(newInterval.start, interval.start);

                newInterval.end = Math.max(newInterval.end, interval.end);

            }

            

        }

        result.add(newInterval);

        return result;

    }

}