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

preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

The array intervals represents a set of several intervals, where a single interval is intervals[I] = [starti, endi]. Combine all the overlapped intervals and return a nonoverlapping array of intervals that cover exactly all the intervals 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].

Example 2: input: intervals = [[1,4],[4,5]] output: [[1,5]] explanation: intervals [1,4] and [4,5] can be considered overlapping intervals.

Link: leetcode-cn.com/problems/me…

Answer key

This problem is simply a problem of merging intervals. The main difficulty is when to merge the preceding and subsequent arrays.

The thing to think about is sorting each array in the intervals by the first element, so that if the current array can be combined with the next, the second element of the current array must be the first element of the next array >=; Otherwise, the two arrays cannot be merged.

With that thought in mind, we can implement it. The key to implementation is how to determine the size of the second element after the merge. If t is large, we add [intrevals[I], t] directly to the resulting array; if t is large, we add [intrevals[I], t] to the resulting array. Otherwise, we go through the next array, and we set t to be the second element in the next array. Until we get to the last array.

See below for specific code implementation.

The time complexity is O(nlogn + n), which is O(nlogn), mainly the time complexity of sorting arrays, and the space complexity is O(1).

/ * * *@param {number[][]} intervals
 * @return {number[][]}* /
var merge = function(intervals) {
    intervals.sort((a, b) = > a[0] - b[0])
    let ans = []
    let i = 0
    let n = intervals.length
    
    while (i < n) {
        let t = intervals[i][1]
        let j = i + 1
        while (j < n && intervals[j][0] <= t) {
            t = intervals[j][1]
            ++j
        }
        ans.push([intervals[i][0], t])
        i = j
    }
    
    return ans
};
Copy the code