This is the 13th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Merge range

This is a set of intervals. A single interval is (intervals[I] = [start I, end I]). Combine all the overlapped intervals and return a nonoverlapping array of intervals that cover exactly all the intervals in the input.

For details, see the LeetCode official website.

Source: LeetCode link: leetcode-cn.com/problems/me… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution 1: recursion

The recursion process is as follows:

  • If the intervals are empty or there is only one element, that is, there is only one interval, there is no need to merge, directly return the intervals;
  • If there are more than 1 intervals, declare a variable that records the length of a dimension (that is, how many intervals there are), a variable called match records the number of intervals that do not need to be merged, and a variable called matchFirst and matchSecond records the two numbers of intervals that currently need to be matched. Then declare a Boolean array flag whether the intervals have been merged, and use a double loop to determine which intervals can be merged. The process is as follows:
    • The outer loop I starts at the first interval, matchFirst and matchSecond record the two values of the interval corresponding to I and add match by 1;
    • The inner loop j starts from the I +1 interval, curFirst and curSecond record the two values of the corresponding interval of J, and then use matchFirst, matchSecond, curFirst, and curSecond to judge whether there is an intersection between I and j. If there is an intersection, Then update the two numbers in the interval I, and update matchFirst and matchSecond, and mark the interval j to true, which means it has been merged; If there is no intersection, the next one is processed;
  • After processing the double loop, judge whether match and length are equal. If they are equal, there is no interval that can be merged, and return intervals; If not, then a new two-dimensional array, newIntervals, is initialized, the intervals that have not been merged (to determine whether they have been merged according to the array of flags) are copied to newIntervals, and then called recursivelymerge(newIntervals).
public class LeetCode_056 {
    public static int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 1) {
            return intervals;
        }
        int length = intervals.length, match = 0, matchFirst, matchSecond;
        boolean[] flag = new boolean[length];

        for (int i = 0; i < length; i++) {
            if(! flag[i]) { matchFirst = intervals[i][0];
                matchSecond = intervals[i][1];
                match++;
                for (int j = i + 1; j < length && ! flag[j]; j++) {int curFirst = intervals[j][0], curSecond = intervals[j][1];
                    if (((matchFirst >= curFirst && matchFirst <= curSecond) || (matchSecond >= curFirst && matchSecond <= curSecond)) ||
                            ((curFirst >= matchFirst && curFirst <= matchSecond) || (curSecond >= matchFirst && curSecond <= matchSecond))) {
                        / / intersection
                        matchFirst = Math.min(matchFirst, curFirst);
                        matchSecond = Math.max(matchSecond, curSecond);
                        intervals[i][0] = matchFirst;
                        intervals[i][1] = matchSecond;
                        flag[j] = true; }}}}if (match == length) {
            return intervals;
        }
        int[][] newIntervals = new int[match][2];
        for (int i = 0, j = 0; i < length; i++) {
            if (!flag[i]) {
                newIntervals[j] = intervals[i];
                j++;
            }
        }
        return merge(newIntervals);
    }
    
    public static void main(String[] args) {
        int[][] intervals = new int[] [] {{1.4}, {2.3}};
        for (int[] ints : merge(intervals)) {
            for (int anInt : ints) {
                System.out.print(anInt + ""); } System.out.println(); }}}Copy the code

When you are not happy, you can eat a piece of candy, and then tell yourself life is still sweet, come on.