[Algorithm Training – Sorting Algorithm 3] [Sort Application] Merge Intervals

Without further ado, just shout a slogan to encourage yourself: Programmers will never be unemployed, programmers go to architecture! The theme of this blog is [Merge Interval], which is implemented using the basic data structure [array]. The site for this high-frequency question is: CodeTop, and the filtering condition is: Target company + Last year + Sort by frequency of occurrence, from high to low, go to Nuke TOP101 to find them. There are only two places where they can be found. Do this question only after it has appeared (CodeTop itself gathers the sources of LeetCode), and make sure that the questions you answer are all frequently asked in interviews.

After clarifying the target question, attach the link to the question. Later, you can practice quickly and repeatedly based on the problem-solving ideas.The questions are classified according to the basic data structure of the question stem, and the first of each category This article must be an introduction to basic data structures.

Merge interval [MID]

A high-frequency question that I have always wanted to solve uses sorting.

Question stem

Problem-solving ideas

If we sort by the left endpoint of the interval, then in the sorted list, the intervals that can be merged must be continuous. As shown in the figure below, the intervals marked blue, yellow and green can be merged into one large interval, and they are continuous in the sorted list.

We use the array merged to store the final answer.

  • First, we sort the ranges in the list in ascending order by left endpoint. We then add the first range to the merged array and consider each subsequent range in order:
  • If the left endpoint of the current interval is after the right endpoint of the last interval in the array merged, then they will not overlap, and we can directly add this interval to the end of the array merged;
  • Otherwise, they overlap, and we need to update the right endpoint of the last interval in the array merged with the right endpoint of the current interval, setting it to the larger of the two.

The general idea is that the left endpoints are arranged from small to large. Each comparison only needs to compare whether the left endpoint of the new interval is after the right endpoint of the merged interval. After that, it is independent, and before it overlaps (and since the left endpoints are in ascending order , it is also in the middle of the previously merged interval. In the extreme case, it overlaps with the left endpoint of the sorted interval)

Code implementation

Give the code to implement the basic file

Basic data structure: Array
Auxiliary data structure: None
Algorithm: Quick sort (divide and conquer algorithm), binary search
Tips: Double pointers

import java.util.*;

/*
 * public class Interval {
 * int start;
 * int end;
 * public Interval(int start, int end) {
 * this.start = start;
 * this.end = end;
 * }
 * }
 */

public class Solution {<!-- -->
    /**
     * The class name, method name, and parameter name in the code have been specified. Please do not modify them. Just return the value specified by the method.
     *
     *
     * @param intervals Interval class ArrayList
     * @return Interval class ArrayList
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {<!-- -->
        // 1 Sort the collection first
        intervals.sort(Comparator.comparingInt(interval -> interval.start));

        // 2 Traverse the sequential array to merge
        ArrayList<Interval> result = new ArrayList<Interval>();
        for (Interval interval : intervals) {<!-- -->
            // 2-1 Get the left and right endpoints of the current interval and the right endpoint of the merged interval
            int leftPoint = interval.start;
            int rightPoint = interval.end;

            // 2-2 If the result interval is empty or the left endpoint of the current interval is greater than the right endpoint of the merged interval, the current interval is added to the set as an independent subinterval.
            if (result.size() == 0 || leftPoint > result.get(result.size() - 1).end) {<!-- -->
                result.add(interval);
            } else {<!-- -->
            // 2-3 Otherwise, it is considered that the current interval overlaps with the merged interval, and only the right endpoint of the merged interval needs to be updated.
                result.get(result.size() - 1).end = Math.max(result.get(result.size() - 1).end, rightPoint);
            }
        }
        return result;
    }
}

How to process leetcode array input parameters:

import java.util.*;


public class Solution {<!-- -->
    /**
     * The class name, method name, and parameter name in the code have been specified. Please do not modify them. Just return the value specified by the method.
     *
     *
     * @param n int integer type the n
     * @return int integer type
     */
    public int[][] merge(int[][] intervals) {<!-- -->
        // 1 Sort the array first
        Arrays.sort(intervals, Comparator.comparingInt(interval->interval[0]));

        // 2 Traverse the sorted array and perform interval merging
        int[][] result = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval : intervals) {<!-- -->
            // 2-1 Get the left and right boundaries of the current interval and the right boundary of the merged interval
            int leftPoint = interval[0];
            int rightPoint = interval[1];

            // 2-2 If the merged interval is empty, or the left endpoint of the current interval is greater than the right endpoint of the merged interval, there will be no overlap.
            if (idx == -1 || result[idx][1] < leftPoint) {<!-- -->
                idx++;
                result[idx] = interval;

            } else {<!-- -->
                // 2-3 Otherwise, they overlap, and the larger value of the two intervals is the new right boundary.
                result[idx][1] = Math.max(result[idx][1], rightPoint);
            }
        }

        return Arrays.copyOf(result, idx + 1);
    }

}

Complexity analysis

Merging intervals is a common algorithm problem, often used to merge intervals with overlapping parts to simplify the problem or provide a clearer representation. The following is a discussion on the time complexity and space complexity of the merging interval problem:

time complexity:
Time complexity is a key measure of algorithm performance and represents the time it takes to run as the input size increases. For the merge interval problem, a common solution is to first sort the intervals by the starting value, and then iterate through these intervals and merge them.

  1. Sorting: Sorting intervals by starting value usually requires O(n*log(n)) time complexity, where n is the number of intervals.

  2. Traversing and merging: Once range sorting is complete, traversing the ranges and merging overlapping portions usually takes linear time, i.e. O(n).

So, taken together, the time complexity of merging intervals is usually O(n*log(n)), where n is the number of intervals. This is dominated by the time complexity of the sorting operation.

Space complexity:
Space complexity represents the additional memory space required by an algorithm during execution. For the merged interval problem, the space complexity usually depends on the data structure that stores the merged intervals.

  1. If you modify in-place on the original interval without creating additional data structures, the space complexity is O(1) because no additional memory space is required.

  2. If you create a new data structure to store the merged ranges, the space complexity will depend on the size of the data structure. Usually, the number of merged intervals will be less than or equal to the initial number of intervals, so the space complexity is also O(n).

Summary: The time complexity of merging interval problems is usually O(n*log(n)), and the space complexity can be O(1) or O(n), depending on whether a new data structure is created to store the merged interval.

Expand knowledge: usage of Arrays

Some usage extensions of Arrays are described below:

Arrays.copyOf(result, x)What does it describe

Arrays.copyOf(result, x) is a Java method. Its meaning is to create a new array with a length of x and copy the original array result are copied into the new array. If x is less than the length of the original array, the new array is truncated to contain only the first x elements of the original array. If x is greater than the length of the original array, the new array will be filled with a default value at the end. This default value depends on the data type of the element. For example, the default value is 0 for numeric types and for reference types. null.

This method allows you to create a new array with a different length without changing the original array, which is very convenient, especially when the array needs to be resized. For example:

int[] result = {<!-- -->1, 2, 3, 4, 5};
int x = 8; // length of new array

int[] newArray = Arrays.copyOf(result, x);

// The new array will now be {1, 2, 3, 4, 5, 0, 0, 0} with length 8

In this example, Arrays.copyOf creates a new array of length 8 and copies the elements in the original array result to the new array, with any excess Fill with 0s.

Arrays.sort(intervals, Comparator.comparingInt(interval->interval[0])) Describe what this statement does

This statement uses the Arrays.sort method in Java to sort a two-dimensional array of intervals. Sorting is based on the value of the first element (interval[0]) of each subarray in the two-dimensional array, that is, sorting is based on the starting value of the subarray.

Specifically, what this line of code does is:

  1. intervals is a two-dimensional array of integers typically used to represent intervals (for example, the start and end values of the interval).

  2. Arrays.sort is a method used in Java to sort arrays.

  3. Comparator.comparingInt(interval -> interval[0]) is a comparator that tells the sorting method to sort by the first element of each subarray (interval[0] ) values are sorted in ascending order.

So, this statement will sort the two-dimensional array based on the first element (the starting value) of each sub-array in intervals, from smallest to largest. After sorting, the subarrays in the intervals array will be arranged in order from small to large starting values.

This is very useful for dealing with interval problems, because it can sort the intervals according to the starting value, making it easier for you to perform various interval operations, such as merging overlapping intervals or finding intervals that contain a certain point.