“This is the fifth day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

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]] explanation: intervals [1,4] and [4,5] can be regarded as overlapping intervals.Copy the code

 

Tip:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

Their thinking

In this case, we need to merge the overlapping intervals and return an array of non-overlapping intervals. Here we can first sort the subarrays of the input array in ascending order by the starting value. This ensures that the starting value of the preceding interval is less than or equal to the starting value of the following interval. At this point, we just need to judge that if the end value of the previous interval is greater than or equal to the start value of the later interval, it means that the two intervals overlap and merge the two intervals. After traversing the sorted input array, judge and merge according to the above logic. After traversing the array, the merged result array is obtained.

The demo

Code implementation

Var string (string, string, string) {string (string, string, string); (enjoyment.length === 1) return enjoyment.sort (enjoyment.length === 1) return enjoyment.sort (enjoyment.length === 1) B) => a[0] -b [0]) // [0], // end = 0; // End = 0; // End = 0; // End = 0; While (tail < len) {// If the start value of the current subinterval is less than or equal to the maximum value of the previous end value of the interval, While (tail < len && intervals[tail][0] <= Max) {// Try to update the maximum value of the end of the interval Max = math.max (Max, [0]) // tail pointer goes back one bit tail++} // If no interval can be found, // Merge intervals are formed from the minimum of the start value and the maximum of the end value of the current interval to merge and insert the result array res.push([min, If (tail < len) {[min, Max] = intervals[tail]}}Copy the code

Here, in the process of coding, we use a small technique, we use a pointer to find the interval that can be merged backwards until we can no longer find the interval that can be merged, and then merge the interval, which reduces the overhead of multiple interval merges.

At this point we have completed the Leetcode-56-merge interval

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻