[LeetCode 56] Merge Intervals (M

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[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].

Example 2:

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

SOLUTION 1: 对start Points 和 end Points 分别排序

1. 所有intervals的题 ，包括meeting rooms，都可以先将given intervals重新拆分成，start points array && end points arrays，然后对其按升序排序。排序以后它的性质其实是不变的，比如该merge的还是merge，meeting rooms该需要几个还是需要几个。
2. 遍历原始given intervals，两两比较, 如果发现有重叠的interval，就记录下起点。 然后继续找，直到没有重叠，记录下endPoint

            int start = startPoints[index];
            
            while (index < intervals.length - 1 && endPoints[index] >= startPoints[index + 1]) {
                index ++;
            }
            
            int end = endPoints[index];

3. 因为整个过程中，start && end在不断更新，如果没有重叠，那么start && end就是原始值，直接构建成一个interval加入结果。如果有重叠，就根据step2，找到start && end，再构建interval加入结果。

Code： Solution1

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0)
            return intervals;
        
        //1. construct a list of start points and a list of end points
        // and sort them on ascending
        int[] startPoints = new int[intervals.length];
        int[] endPoints = new int[intervals.length];
        
        for (int i = 0; i < intervals.length; i ++) {
            startPoints[i] = intervals[i][0];
            endPoints[i] = intervals[i][1];
        }
        
        Arrays.sort (startPoints);
        Arrays.sort (endPoints);
        
        //2. merge 
        List<int[]> result = new ArrayList<> ();
        
        int index = 0;
        while (index < intervals.length) {
            int start = startPoints[index];
            
            while (index < intervals.length - 1 && endPoints[index] >= startPoints[index + 1]) {
                index ++;
            }
            
            int end = endPoints[index];
            
            int[] newInterval = new int[] {start, end};
            result.add (newInterval);
            
            index ++;
        }
        
        
        return convertResult (result);
    }
    
    public int[][] convertResult (List<int[]> list) {
        int[][] result = new int[list.size ()][2];
        
        for (int i = 0; i < list.size (); i++) {
            result[i] = list.get (i);
        }
        
        return result;
    }
}

Solution2： 对原始intervals 按照start point排序

https://www.youtube.com/watch?v=ewD9OwjsU3w

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0)
            return intervals;
        // SOlution 1 (不是那么好理解)
        /*
        //1. construct a list of start points and a list of end points
        // and sort them on ascending
        int[] startPoints = new int[intervals.length];
        int[] endPoints = new int[intervals.length];
        
        for (int i = 0; i < intervals.length; i ++) {
            startPoints[i] = intervals[i][0];
            endPoints[i] = intervals[i][1];
        }
        
        Arrays.sort (startPoints);
        Arrays.sort (endPoints);
        
        //2. merge 
        List<int[]> result = new ArrayList<> ();
        
        int index = 0;
        while (index < intervals.length) {
            int start = startPoints[index];
            
            while (index < intervals.length - 1 && endPoints[index] >= startPoints[index + 1]) {
                index ++;
            }
            
            int end = endPoints[index];
            
            int[] newInterval = new int[] {start, end};
            result.add (newInterval);
            
            index ++;
        }
        
        
        return convertResult (result);
        */
        
        /// Solution 2: sort intervals based on startPoints
        Arrays.sort (intervals, (int[] entry1, int[] entry2) -> (entry1[0] - entry2[0]));
        
        List<int[]> result = new ArrayList<> ();
        
        for (int i = 0; i < intervals.length; i ++) {
            if (result.size () == 0) {
                result.add (intervals[i]);
                continue;
            }
            
            if (intervals[i][0] <= result.get (result.size () - 1)[1]) {
                result.get (result.size () - 1)[1] = Math.max (intervals[i][1], result.get (result.size () - 1)[1]);
            } else {
                result.add (intervals[i]);
            }
        }
        
        return convertResult (result);
    }
    
    public int[][] convertResult (List<int[]> list) {
        int[][] result = new int[list.size ()][2];
        
        for (int i = 0; i < list.size (); i++) {
            result[i] = list.get (i);
        }
        
        return result;
    }
}