Leetcode: Merge Intervals

 This question might be, if not the most common, one of the most common interview questions there is, since it was asked very frequently at Facebook, Bloomberg, Amazon, and Google. The question is as follows:

Given an array of intervals where intervals[i] = [starti, endi], merge all the overlapping intervals and return an array of the nonoverlapping intervals inside of the input. The interval length cannot be greater than 10000, each array length, cannot be greater than 3. The start and end intervals also have to be less than 10^4. Here are the sample problems:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Now time for the intuition behind the solution. We try to sort the intervals by their starting points and merge accordingly. This way, at each starting point, We can simply check the beginning to see if it is inside of the previous interval. Since sorting takes O(n log n) and merging takes O(n) the result takes O(n) + O(n log n) which is just O(n log n). We create a list and move the end if needed if there is an overlapping interval and just add the interval to the list if there is a disjoint interval. Here is the resulting code: 

class Solution {

    public int[][] merge(int[][] intervals) {

        if(intervals.length <= 1) return intervals;

        Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0])); //sort using this or merge sort.

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

        int[] newInterval = intervals[0]; 

        result.add(newInterval);

        for(int[] interval : intervals) {

            if(interval[0] <= newInterval[1])

                newInterval[1] = Math.max(newInterval[1], interval[1]);

            else {

                newInterval = interval;

                result.add(newInterval);

            }

        }

        return result.toArray(new int[result.size()][]);

    }

}