Array represents a collection of several intervals. Please merge all overlapping intervals and return a non overlapping interval array. The array must exactly cover all the intervals in the input. 【Le

Force deduction hot question 100 The first 56 topic ： Merge range

Post the code first ：

class Solution {
    public int[][] merge(int[][] intervals) {
        //  First pair  intervals  Array to sort 
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        //  Create array  list  Store merged intervals 
        List<int[]> list = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; i++) {
            int L = intervals[i][0], R = intervals[i][1];
            if (list.size() == 0 || list.get(list.size() - 1)[1] < L) {
                list.add(new int[]{L, R});
            } else {
                list.get(list.size() - 1)[1] = Math.max(list.get(list.size() - 1)[1], R);
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

Their thinking ：

         In this question, we are required to merge all the mergeable intervals , What do you mean by a range that can be merged ？ If these two intervals intersect , Then it belongs to the mergeable interval . For example, the example in the title ：[  [1,3] , [2,6] , [8,10] , [15,18]  ], On the horizontal coordinate line, it is shown as follows ：

         You can see , In the above four intervals , Only the red section and the green section overlap , That is, there is intersection , So it means the red range [1,3] And the green zone [2,6] Is mergeable , The merged interval is [1,6] .

         After understanding the meaning of the question , How to solve this problem ？

        Let's first understand the conditions under which two intervals can be merged , Because the above figure shows , When two intervals intersect , Is mergeable , And when two intervals , When an interval is a subset of another interval , These two intervals can also be merged . So when two intervals can be merged , The condition is that the maximum value of the previous interval is greater than the minimum value of the next interval , Or an interval contains another interval . From this we can judge that , When the minimum values of two intervals are arranged from small to large , Just judge the size of the maximum value .

        From this, we can get the idea of solving problems , First, arrange the intervals in the array from small to large according to the minimum value , So if two intervals can be merged , Then these two intervals must be continuous ！ Because of the array in the title intervals Is a two-dimensional array , So you need to use... When sorting lambda expression ：

         Or we could just write it as ：

        So that we can intervals The array is arranged according to the minimum value of the interval , Then we'll create a new one list To store the merged Section .