Preface

Today's clock in algorithm problem , Draw to the consolidation interval , Take it as the carrier , Show my personal understanding of problem solving .

One 、 Merge range

Two 、 Explain

1、idea

target： Merge repeated intervals .

Personally, I think the ability to grasp the core issues is the pre ability ：1- What is a repeating interval ？2- What will the merger look like ？

1- What is a repeating interval ？ Set interval [a,b] and [c,d], When a > d || b < c Time does not repeat ; conversely a <= d && b >= c Then the two intervals repeat .
2- What will the merger look like ？ There are conditions for determining the repetition interval , It needs to be merged into [min(a,c),max(b,d)]

Actual scheme 1 ： Violence law ： Merge the two intervals in the above way , New areas join list, Combined 2 Intervals remove fall .O(N)/O(N)

Personally think that ： Routines are tools , To solve the core problem we found .
There is a routine ： A routine of two-dimensional arrays like this is , Most of them need the first and second elements to order / The reverse .

Actual scheme II ： Sequencing ： In order to prevent finding all the intervals to merge each time , Sort the intervals , Naturally, the merged interval will not be considered , The remaining intervals only need to be merged one by one .（ Make use of man-made order .）

2、code

package everyday.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//  Interval merging 
public class Merge {
    
    /* target： Merge repeated intervals .  Personally, I think the ability to grasp the core issues is the pre ability ：1- What is a repeating interval ？2- What will the merger look like ？ 1- What is a repeating interval ？ Set interval [a,b] and [c,d], When  a > d || b < c  Time does not repeat ; conversely a <= d && b >= c Then the two intervals repeat . 2- What will the merger look like ？ There are conditions for determining the repetition interval , It needs to be merged into [min(a,c),max(b,d)]  Violence law ： Merge the two intervals in the above way , New areas join list, Combined 2 Intervals remove fall .O(N)/O(N)  Personally think that ： Routines are tools , To solve the core problem we found .  There is a routine ： A routine of two-dimensional arrays like this is , Most of them need the first and second elements to order / The reverse .  Sequencing ： In order to prevent finding all the intervals to merge each time , Sort the intervals , Naturally, the merged interval will not be considered , The remaining intervals only need to be merged one by one .（ Make use of man-made order .） */
    public int[][] merge(int[][] intervals) {
    
        Arrays.sort(intervals, (o1, o2) -> {
    
            if (o1[0] != o2[0]) return o1[0] - o2[0];

            return o1[1] - o2[1];
        });
        List<int[]> ans = new ArrayList<>();
        int[] cur = new int[]{
    intervals[0][0], intervals[0][1]};

        for (int i = 1; i < intervals.length; i++) {
    
            int a = cur[0], b = cur[1], c = intervals[i][0], d = intervals[i][1];

            if (a > d || b < c) {
    
                ans.add(new int[]{
    a, b});

                cur[0] = c;
                cur[1] = d;

                continue;
            }
            cur[1] = Math.max(b, d);
        }
        ans.add(cur);

        return ans.toArray(new int[0][]);
    }
}

summary

1. Focus on core issues , The solutions are all centered on solving the core problems .
2. The routine of two-dimensional array , It needs to be sorted first , With order , Think of double pointers / The sliding window / Dichotomy, etc .

reference

[1] LeetCode 56. Merge range