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

Topic describes

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 <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

Topic link: Merge interval

Thinking is introduced

Let the initial value of interval A be the first interval, and let interval B be each interval traversed in intervals. The intervals array is traversed, and interval A is compared with interval B: When interval A is greater than or equal to the left of interval B, merging conditions are met; when the right of interval A is greater than or equal to the right of interval B, there is no need to merge, and the traversal can be continued downward. When the right side of interval A is less than the right side of interval B, merge. When the right side of interval A is smaller than the left side of interval B, store interval A in List and update interval A, even if index pointer points to interval B, finally the List will be converted into a two-dimensional array

For example: [[1,3],[2,6],[8,10],[15,18]] 1, start = 1 and end = 3 2, [2,6], find 2 (new start) < 3 (the end of the previous one), prove that the two nodes directly overlap to merge. Math.max(3, 6) = 6 3. In [8, 10], it is found that 8 (new start) > 6 (end of the previous one), indicating that there is no intersection between the two intervals. In this case, save [start, end], i.e. [1,6], which is the result of the combination of the first two intervals. After saving, update start = 8, end = 10; 4. To [15, 18], it is found that 15 > 10, indicating that there is no intersection between the two intervals. Save [start,end], namely [8,10], which is the last non-overlapping interval. Then update start = 15, end = 18. 5. After traversal, save the current [start,end], which is the last interval

code

class Solution { public int[][] merge(int[][] intervals) { List<int[]> ans = new ArrayList<>(); Arrays.sort(intervals, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]); int start = intervals[0][0], end = intervals[0][1]; for (int i = 1; i < intervals.length; i++){ if (intervals[i][0] <= end){ end = Math.max(end, intervals[i][1]); }else{ ans.add(new int[] {start, end}); start = intervals[i][0]; end = intervals[i][1]; } } ans.add(new int[] {start, end}); int[][] res = new int[ans.size()][2]; for (int i = 0; i < res.length; i++){ res[i] = ans.get(i); } return res; }}Copy the code

The results

Result: Yes

Execution time: 6 ms,

Memory consumption: 46.2MB