Leetcode: Insert Interval

 Here is a question that Google, Twitter, and Amazon like to ask.

Given a set of non-overlapping intervals, inter a new interval into the intervals and merge if necessary. You may assume that the intervals were initially sorted according to their start times. 

The length of the intervals go from 0 to 10,000 and each array index of the intervals have a length of 2. Each interval can go all the way to the number 100,000 and is sorted in ascending order. Here are the sample cases: 

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

Example 3:

Input: intervals = [], newInterval = [5,7]

Output: [[5,7]]

Example 4:

Input: intervals = [[1,5]], newInterval = [2,3]

Output: [[1,5]]

Example 5:

Input: intervals = [[1,5]], newInterval = [2,7]

Output: [[1,7]]

We add all the intervals ending before the newIntervals starts, merge all the overlapping intervals into the new intervals and add this union, and add the remainder of these intervals. Here's the code. This solution inserts first, then merges.

class Solution {

    public int[][] insert(int[][] intervals, int[] newInterval) {

            if(intervals == null || intervals.length == 0) return new int[][]{newInterval};

            //add this to the final list and then result.

            final int[][] newIntervals = new int[intervals.length + 1][2];

            int index = 0;

            boolean inserted = false;

            //iterate through all of the intervals.

            for(int i = 0; i < intervals.length; i++){

                //Insert the beginning of the interval at the corresponding location

                if(newInterval[0] <= intervals[i][0] && !inserted) {

                    newIntervals[index++] = newInterval;

                    inserted = true;

                }

                //insert the remainder of the intervals

                newIntervals[index++] = intervals[i];

            }

            if(!inserted) newIntervals[index] = newInterval;

            final List<int[]> list = new ArrayList<>();

            //add the first element

            list.add(newIntervals[0]);

            //go forwards on the list and find the value where the current interval is greater than last interval, this is when to add this particular index, and update this interval.

            for(int i = 1; i < newIntervals.length; i++) {

                final int[] lastInterval = list.get(list.size() - 1);

                final int[] currentInterval = newIntervals[i];

                if(currentInterval[0] <= lastInterval[1]) {

                    lastInterval[1] = Math.max(lastInterval[1], currentInterval[1]);

                } else {

                    list.add(currentInterval);

                }

            }

        for(int i = 0; i < list.size(); i++) {

            result[i] = list.get[i];

        }

        return result; 

    }

}