# subject

Given a set of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
Interpretation: The intervals [1,3] and [2,6] overlap and merge them into [1,6].


Example 2:

Input: [[1,4], [4,5]]
Output: [[1,5]]
Interpretation: Intervals [1,4] and [4,5] can be considered overlapping intervals.


Source: LeetCode

## Solving problems

### Idea 1 - Sort by starting position of intervals, then merge in order

Steps:

1. Sort in ascending order by the starting position of the interval, create a new result array RST with the same length as the source array, and add the first interval, where the rst length is k=1;
2. From the second interval, check if the left boundary of each interval is within the right boundary of the last interval of rst (<=), then merge, otherwise the rst is enhanced and k++;
3. The part that returns the actual length of the rst is the merge result.

Algorithmic complexity: N is the total number of intervals

• Time complexity: ${\color{Magenta}{\Omicron\left(NlogN\right)}$
• Spatial Complexity: ${\color{Magenta}{\Omicron\left(NlogN\right)}$- Space required for sorting other than result array

### Idea 2 - No sorting, direct check merge

Steps:

1. The outer loop starts with i, the inner loop starts with j=i+1, and count records the number of merges;
2. Try to merge i into j and update j to destroy i (null) and count++, if mergeable;
3. If count=0 returns the source array directly, otherwise taking out all non-null intervals as a new array is the result.

Algorithmic complexity: N is the total number of intervals

• Time complexity: ${\color{Magenta}{\Omicron\left(N^{2}\right)}$
• Spatial Complexity: ${\color{Magenta}{\Omicron\left(1\right)}$- except for result array

## Sample algorithm source

package leetcode;

import java.util.Arrays;
import java.util.Comparator;

/**
* @author ZhouJie
* @date 2020 February 21, 2000 5:57:22 p.m.
* @Description: 56. Consolidation interval
*
*/
public class LeetCode_0056 {

}

class Solution_0056 {
/**
* @author: ZhouJie
* @date: 2020 February 21, 2000 6:40:28 p.m.
* @param: @param <T>
* @param: @param intervals
* @param: @return
* @return: int[][]
* @Description: 1-
*
*/
public int[][] merge_1(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return intervals;
}
// Sort ascending by left boundary
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1 - o2;
}
});
int len = intervals.length;
int[][] rst = new int[len];
rst = intervals;
int k = 0;
for (int i = 1; i < len; i++) {
int x1 = intervals[i];
int y1 = intervals[i];
int y2 = rst[k];
// If the left boundary of i is less than or equal to the right boundary of the last interval of rst, then i can be merged or not added
if (x1 <= y2) {
rst[k] = Math.max(y1, y2);
} else {
rst[++k] = intervals[i];
}
}
return Arrays.copyOf(rst, ++k);
}

/**
* @author: ZhouJie
* @date: 2020 March 4, 2000 6:45:34 p.m.
* @param: @param intervals
* @param: @return
* @return: int[][]
* @Description: 2-Gradually merge backwards to filter and return;
*
*/
public int[][] merge_2(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return intervals;
}
int len = intervals.length;
int count = 0;
// The interval j comparison after i and i is taken each time, if it can be merged, i is merged into j and i itself is null marked
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
int x1 = intervals[i];
int y1 = intervals[i];
int x2 = intervals[j];
int y2 = intervals[j];
int l = Math.min(x1, x2);
int r = Math.max(y1, y2);
// To determine whether or not the ij intervals can be merged: if the maximum boundary distance of the ij intervals is less than or equal to the sum of the spans of the ij intervals, the ij intervals can be merged or overlapped
if (r - l <= y1 - x1 + y2 - x2) {
intervals[j] = l;
intervals[j] = r;
// After merging, the i-interval null marker
intervals[i] = null;
// Count the number of merges used to determine and define the length of the result array
count++;
break;
}
}
}
// Not merged, returning directly to the original array
if (count == 0) {
return intervals;
} else {
// Merge over, create a new array, skip null, store and return the merged array
int[][] rst = new int[len - count][];
int k = 0;
for (int[] t : intervals) {
if (t != null) {
rst[k++] = t;
}
}
return rst;

}
}
}


Posted on Fri, 17 Apr 2020 09:50:10 -0700 by naitsir