LeetCode 56. Consolidated intervals

My LeetCode: https://leetcode-cn.com/u/ituring/

My LeetCode brush Title source [GitHub]: https://github.com/izhoujie/Algorithmcii

LeetCode 56. Consolidated intervals

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
Links: https://leetcode-cn.com/problems/merge-intervals
Copyright shall be owned by the withholding network.For commercial reprinting, please contact the official authorization. For non-commercial reprinting, please indicate the source.

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[0] - o2[0];
			}
		});
		int len = intervals.length;
		int[][] rst = new int[len][2];
		rst[0] = intervals[0];
		int k = 0;
		for (int i = 1; i < len; i++) {
			int x1 = intervals[i][0];
			int y1 = intervals[i][1];
			int y2 = rst[k][1];
			// 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][1] = 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][0];
				int y1 = intervals[i][1];
				int x2 = intervals[j][0];
				int y2 = intervals[j][1];
				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][0] = l;
					intervals[j][1] = 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;

		}
	}
}

Tags: Java github less network

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