原文地址：【题目】合并区间

题目名称

合并区间

题目地址

https://leetcode-cn.com/problems/merge-intervals/

题目描述

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

  
 

  
1
  
2
  
3
 

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

  
 

  
1
  
2
  
3
 

解题源码

方法一

先排序，后遍历

源码

public class Topic56_1 { public static void main(String[] args) { int[][] a = new int[4][2]; a[0][0] = 1; a[0][1] = 3; a[1][0] = 2; a[1][1] = 6; a[2][0] = 5; a[2][1] = 10; a[3][0] = 15; a[3][1] = 18; int[][] b = merge(a); for (int i=0;i<b.length;i++){ System.out.println(b[i][0]+","+b[i][1]); } } public static int[][] merge(int[][] intervals) { //先将intervals进行排序,按照第一列的顺序 quickSort(intervals);

// for (int i=0;i<intervals.length;i++){
// System.out.println(intervals[i][0]+","+intervals[i][1]);
// } int[][] b = new int[intervals.length][2]; int bIndex = 0; for (int i=0;i<intervals.length;i++){ int left = intervals[i][0]; int right = intervals[i][1]; // i不能到最后一行,所以要小于(数组的长度 - 1) // 判断所在行的right和下一行的left大小,对right重新进行赋最大值,之后再不断进行while循环判断 while (i < intervals.length - 1 && right >= intervals[i + 1][0]) { i++; right = Math.max(right, intervals[i][1]); } b[bIndex][0] = left; b[bIndex][1] = right; bIndex++; } int[][] rb = new int[bIndex][2]; //截断b数组 System.arraycopy(b, 0, rb, 0,bIndex); return rb; } public static void quickSort(int[][] arr){ quickSort(arr, 0, arr.length-1); } private static int partition(int[][] arr, int left, int right) { int temp = arr[left][0]; int temp1 = arr[left][1]; while (right > left) { // 先判断基准数和后面的数依次比较 while (temp <= arr[right][0] && left < right) { --right; } // 基准数大于了 arr[right] if (left < right) { temp(arr, right, arr[left]); ++left; } //  基准数大于了 arr[left] while (temp >= arr[left][0] && left < right) { ++left; } if (left < right) { temp(arr, left, arr[right]); --right; } } arr[left][0] = temp; arr[left][1] = temp1; return left; } private static void temp(int[][] arr, int left, int[] ints) { int tempA = ints[0]; int tempB = ints[1]; ints[0] = arr[left][0]; ints[1] = arr[left][1]; arr[left][0] = tempA; arr[left][1] = tempB; } private static void quickSort(int[][] arr, int left, int right) { if (arr == null || left >= right || arr.length <= 1) { return; } int mid = partition(arr, left, right); quickSort(arr, left, mid); quickSort(arr, mid + 1, right); }

}
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
 

消耗

9 ms 41.3 MB

方法二

直接遍历

源码

public class Topic56_2 { public static void main(String[] args) { int[][] a = new int[3][2]; a[0][0] = 1; a[0][1] = 4; a[1][0] = 0; a[1][1] = 2; a[2][0] = 3; a[2][1] = 5; int[][] b = merge(a); for (int i=0;i<b.length;i++){ System.out.println(b[i][0]+","+b[i][1]); } } public static int[][] merge(int[][] intervals) { int len = intervals.length; for (int i=0;i<len-1;i++){ if(intervals[i]==null){ continue; } int min = intervals[i][0]; int max = intervals[i][1]; for(int j=i+1;j<len;j++){ if(intervals[j]==null){ continue; } int a = intervals[j][0]; int b = intervals[j][1]; if( (a>=min && a<=max) || (b>=min && b<=max) || (min<=b && min>=a) || (max<=b && max>=a)  ){ intervals[j][0] = Math.min(min,a); intervals[j][1] = Math.max(max,b); intervals[i]=null; } } } int[][] rb = new int[len][2]; int ind = 0; for (int[] interval : intervals) { if (interval != null) { rb[ind] = interval; ind++; } } int[][] real = new int[ind][2]; System.arraycopy(rb,0,real,0,ind); return real; }
}
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
 

消耗

206 ms 42.8 MB

方法还有很多，上面的也不是最优解。上面仅是我的两种解题源码，仅供参考

吾非大神，与汝俱进

文章来源: chenhx.blog.csdn.net，作者：谙忆，版权归原作者所有，如需转载，请联系作者。

原文链接：chenhx.blog.csdn.net/article/details/101062025