LeetCode 56. 合并区间
题目描述
🔥 56. 合并区间
思路分析
解题思路：
- 首先，对区间按照起始位置进行排序，这样可以将重叠的区间排列在一起。
- 遍历排序后的区间列表，用一个新的列表来存储合并后的区间。初始时，将第一个区间加入新列表。
- 对于每个区间，判断其与新列表中最后一个区间是否重叠。如果重叠，更新新列表中最后一个区间的结束位置为当前区间的结束位置和原最后区间结束位置的较大值。如果不重叠，将当前区间加入新列表。
- 最后返回新列表，其中包含合并后的区间。
参考代码
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
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return [][]int{}
}
sort.SliceStable(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
res := [][]int{intervals[0]}
for i := 1; i < len(intervals); i++ {
cur := intervals[i]
if cur[0] <= res[len(res)-1][1] {
res[len(res)-1][1] = max(res[len(res)-1][1], cur[1])
} else {
res = append(res, cur)
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
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
func merge(intervals [][]int) [][]int {
res := make([][]int, 0)
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
pre := intervals[0]
for i := 1; i < len(intervals); i++ {
cur := intervals[i]
if pre[1] < cur[0] {
res = append(res, pre)
pre = cur
} else {
pre[1] = max(pre[1], cur[1])
}
}
res = append(res, pre)
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
int n = intervals.length;
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
int[] pre = intervals[0];
for (int i = 1; i < n; i++) {
int[] cur = intervals[i];
if (pre[1] < cur[0]) {
res.add(pre);
pre = cur;
} else {
pre[1] = Math.max(pre[1], cur[1]);
}
}
res.add(pre);
return res.toArray(new int[res.size()][]);
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！