“This is my 37th day of participating in the First Challenge 2022. For details: First Challenge 2022”

The title

The array enjoyments is a set of intervals, where a single interval is enjoyments [I] = [Starti, endi]. You merge all overlapping ranges and return a non-overlapping array of ranges that exactly covers all of the ranges in the input.

Example 1:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 17]] output: [[1, 6], [8, 10], [15, 17]] : interval [1, 3] and [2, 6] overlap, merge them into [1, 6].Copy the code

Example 2:

Input: intervals = [[1, 4], [4, 5]] output: [[1, 5]] : interval [1, 4] and [4, 5] can be seen as overlapping range.Copy the code

Tip:

1 < = intervals. Length < = 10 4 power of intervals [I] length = = 2 0 < = force < = endi < = 4 power of 10Copy the code

Source: LeetCode link: leetcode-cn.com/problems/me… Copyright belongs to the Collar buckle network.

Their thinking

  1. Convert the range to parentheses: The left range is converted to make parentheses[l, 1], the right interval is converted to a close parenthesis[r, -1].
  2. The conversion results are then sorted, ascending by number first, descending by parentheses if the number is the same.
  3. When the sum is 0, it indicates that the left and right parentheses match, and the last number and the current number are a combined interval.

Example 1 [[1, 3], [2, 6], [8, 10], [15, 17]] of the process, as shown in [1, 3] and [2, 6] merged into a range.

Code implementation

var merge = function(intervals) {
    const arr = []

    // Convert the interval into parentheses, with 1 representing the left parenthesis and -1 representing the right parenthesis
    for (const [l, r] of intervals) {
        arr.push([l, 1])
        arr.push([r, -1])}// Sort: ascending by range number first, inverted by parentheses if array is the same
    arr.sort((a, b) = > a[0] === b[0]? b[1] - a[1] : a[0] - b[0])

    const ans = []
    let l = -1  // Record the number to the left of the range
    let sum = 0 // aggregate the sum of parentheses

    for (const [a, b] of arr) {
        // If desired, set a to the left of the range
        if (l === -1) l = a

        // Aggregate the values of parentheses
        sum += b

        [l, a] is a valid merged interval
        if (sum === 0) {
            ans.push([l, a])
            // Reset the left parenthesis to -1
            l = -1}}return ans
};
Copy the code

If there are mistakes welcome to point out, welcome to discuss together!