题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = $[start_i, end_i]$ 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]。
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
- $1 <= intervals.length <= 10^4$
- intervals[i].length == 2
- $0 <= start_i <= end_i <= 10^4$
解决方法
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return {};
}
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
return a[0] < b[0];
});
vector<vector<int>> merged = {intervals[0]};
for (int i = 1; i < intervals.size(); ++i) {
const auto& current_interval = intervals[i];
auto& last_merged_interval = merged.back();
if (current_interval[0] <= last_merged_interval[1]) {
last_merged_interval[1] = max(last_merged_interval[1], current_interval[1]);
} else {
merged.push_back(current_interval);
}
}
return merged;
}
};
|
结果
执行用时 : 28 ms, 击败 76.03% 使用 C++ 的用户
内存消耗 : 22.21 MB, 击败 26.87% 使用 C++ 的用户
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return new int[0][];
}
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
merged.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] currentInterval = intervals[i];
int[] lastMergedInterval = merged.get(merged.size() - 1);
if (currentInterval[0] <= lastMergedInterval[1]) {
lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
} else {
merged.add(currentInterval);
}
}
return merged.toArray(new int[merged.size()][]);
}
}
|
结果
执行用时 : 7 ms, 击败 82.65% 使用 Java 的用户
内存消耗 : 45.46 MB, 击败 33.21% 使用 Java 的用户
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for i in range(1, len(intervals)):
current_interval = intervals[i]
last_merged_interval = merged[-1]
if current_interval[0] <= last_merged_interval[1]:
last_merged_interval[1] = max(last_merged_interval[1], current_interval[1])
else:
merged.append(current_interval)
return merged
|
结果
执行用时 : 36 ms, 击败 49.08% 使用 Python 的用户
内存消耗 : 15.06 MB, 击败 80.24% 使用 Python 的用户
Python3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for i in range(1, len(intervals)):
current_interval = intervals[i]
last_merged_interval = merged[-1]
if current_interval[0] <= last_merged_interval[1]:
last_merged_interval[1] = max(last_merged_interval[1], current_interval[1])
else:
merged.append(current_interval)
return merged
|
结果
执行用时 : 59 ms, 击败 26.44% 使用 Python3 的用户
内存消耗 : 19.45 MB, 击败 73.68% 使用 Python3 的用户
C
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
| struct vat {
int start;
int end;
};
int compare(const void* a, const void* b) {
return (((struct vat*)a)->start < ((struct vat*)b)->start) ? -1 : (((struct vat*)a)->start > ((struct vat*)b)->start) ? 1 : 0;
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
struct vat* newVat = (struct vat*)malloc(intervalsSize * sizeof(struct vat));
for (int i = 0; i < intervalsSize; i++) {
newVat[i].start = intervals[i][0];
newVat[i].end = intervals[i][1];
}
qsort(newVat, intervalsSize, sizeof(struct vat), compare);
int** returnInteval = (int**)malloc(sizeof(int*) * intervalsSize);
*returnColumnSizes = (int*)malloc(sizeof(int) * intervalsSize);
*returnSize = 0;
for (int i = 0; i < intervalsSize; i++) {
if (*returnSize) {
int preEnd = returnInteval[*returnSize - 1][1];
if (newVat[i].start <= preEnd) {
int maxEnd = (preEnd > newVat[i].end) ? preEnd : newVat[i].end;
returnInteval[*returnSize - 1][1] = maxEnd;
} else {
int newRow = *returnSize;
returnInteval[newRow] = (int*)malloc(sizeof(int) * 2);
returnInteval[newRow][0] = newVat[i].start;
returnInteval[newRow][1] = newVat[i].end;
(*returnColumnSizes)[newRow] = 2;
*returnSize = *returnSize + 1;
}
} else {
int newRow = *returnSize;
returnInteval[newRow] = (int*)malloc(sizeof(int) * 2);
returnInteval[newRow][0] = newVat[i].start;
returnInteval[newRow][1] = newVat[i].end;
(*returnColumnSizes)[newRow] = 2;
*returnSize = *returnSize + 1;
}
}
returnInteval = (int**)realloc(returnInteval, (*returnSize) * sizeof(int*));
free(newVat);
return returnInteval;
}
|
结果
执行用时 : 49 ms, 击败 88.06% 使用 C 的用户
内存消耗 : 12.22 MB, 击败 77.87% 使用 C 的用户
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public class Solution {
public int[][] Merge(int[][] intervals) {
if (intervals == null || intervals.Length == 0) {
return new int[0][];
}
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
List<int[]> mergedIntervals = new List<int[]>();
int[] currentInterval = intervals[0];
for (int i = 1; i < intervals.Length; i++) {
if (currentInterval[1] >= intervals[i][0]) {
currentInterval[1] = Math.Max(currentInterval[1], intervals[i][1]);
} else {
mergedIntervals.Add(currentInterval);
currentInterval = intervals[i];
}
}
mergedIntervals.Add(currentInterval);
return mergedIntervals.ToArray();
}
}
|
结果
执行用时 : 134 ms, 击败 96.73% 使用 C# 的用户
内存消耗 : 55.09 MB, 击败 38.56% 使用 C# 的用户
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
var merge = function(intervals) {
if (!intervals || intervals.length === 0) {
return [];
}
intervals.sort((a, b) => a[0] - b[0]);
let mergedIntervals = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
let currentInterval = intervals[i];
let lastMergedInterval = mergedIntervals[mergedIntervals.length - 1];
if (currentInterval[0] <= lastMergedInterval[1]) {
lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
} else {
mergedIntervals.push(currentInterval);
}
}
return mergedIntervals;
};
|
结果
执行用时 : 91 ms, 击败 68.92% 使用 JavaScript 的用户
内存消耗 : 56.80 MB, 击败 38.99% 使用 JavaScript 的用户
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function merge(intervals: number[][]): number[][] {
if (!intervals || intervals.length === 0) {
return [];
}
intervals.sort((a, b) => a[0] - b[0]);
const mergedIntervals: number[][] = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const currentInterval = intervals[i];
const lastMergedInterval = mergedIntervals[mergedIntervals.length - 1];
if (currentInterval[0] <= lastMergedInterval[1]) {
lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
} else {
mergedIntervals.push(currentInterval);
}
}
return mergedIntervals;
}
|
结果
执行用时 : 90 ms, 击败 84.93% 使用 TypeScript 的用户
内存消耗 : 57.93 MB, 击败 32.46% 使用 TypeScript 的用户
PHP
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
| class Solution {
function merge($intervals) {
if (empty($intervals)) {
return [];
}
sort($intervals);
$mergeArray = [$intervals[0]];
foreach ($intervals as $interval) {
$start = $interval[0];
$end = $interval[1];
$lastMergedInterval = &$mergeArray[count($mergeArray) - 1];
if ($start <= $lastMergedInterval[1]) {
$lastMergedInterval[1] = max($lastMergedInterval[1], $end);
} else {
$mergeArray[] = $interval;
}
}
return $mergeArray;
}
}
|
结果
执行用时 : 48 ms, 击败 75.00% 使用 PHP 的用户
内存消耗 : 28.94 MB, 击败 50.00% 使用 PHP 的用户
Swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
func merge(_ intervals: [[Int]]) -> [[Int]] {
if intervals.isEmpty {
return []
}
let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
var mergeArray = [sortedIntervals[0]]
for interval in sortedIntervals {
let start = interval[0]
let end = interval[1]
if start <= mergeArray.last![1] {
mergeArray[mergeArray.count - 1][1] = max(mergeArray.last![1], end)
} else {
mergeArray.append(interval)
}
}
return mergeArray
}
}
|
结果
执行用时 : 63 ms, 击败 96.53% 使用 Swift 的用户
内存消耗 : 17.29 MB, 击败 20.14% 使用 Swift 的用户
Kotlin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
fun merge(intervals: Array<IntArray>): Array<IntArray> {
if (intervals.isEmpty()) {
return emptyArray()
}
val sortedIntervals = intervals.sortedBy { it[0] }
val mergeArray = mutableListOf(sortedIntervals[0])
for (interval in sortedIntervals) {
val start = interval[0]
val end = interval[1]
if (start <= mergeArray.last()[1]) {
mergeArray.last()[1] = maxOf(mergeArray.last()[1], end)
} else {
mergeArray.add(interval)
}
}
return mergeArray.toTypedArray()
}
}
|
结果
执行用时 : 345 ms, 击败 24.69% 使用 Kotlin 的用户
内存消耗 : 48.93 MB, 击败 18.52% 使用 Kotlin 的用户
Dart
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
List<List<int>> merge(List<List<int>> intervals) {
if (intervals == null || intervals.isEmpty) {
return [];
}
intervals.sort((a, b) => a[0] - b[0]);
List<List<int>> mergeArray = [intervals[0]];
for (List<int> interval in intervals) {
int start = interval[0];
int end = interval[1];
if (start <= mergeArray.last[1]) {
mergeArray.last[1] = mergeArray.last[1].compareTo(end) > 0
? mergeArray.last[1]
: end;
} else {
mergeArray.add([start, end]);
}
}
return mergeArray;
}
}
|
结果
执行用时 : 344 ms, 击败 88.89% 使用 Dart 的用户
内存消耗 : 153.66 MB, 击败 100.00% 使用 Dart 的用户
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return [][]int{}
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
merged := [][]int{intervals[0]}
for _, interval := range intervals {
start, end := interval[0], interval[1]
if start <= merged[len(merged)-1][1] {
merged[len(merged)-1][1] = max(merged[len(merged)-1][1], end)
} else {
merged = append(merged, []int{start, end})
}
}
return merged
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
|
结果
执行用时 : 15 ms, 击败 79.75% 使用 Go 的用户
内存消耗 : 6.43 MB, 击败 29.05% 使用 Go 的用户
Ruby
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def merge(intervals)
return [] if intervals.empty?
intervals.sort! { |a, b| a[0] - b[0] }
merged = [intervals[0]]
intervals.each do |interval|
start, end_point = interval
if start <= merged.last[1]
merged.last[1] = [merged.last[1], end_point].max
else
merged << [start, end_point]
end
end
merged
end
|
结果
执行用时 : 102 ms, 击败 50.00% 使用 Ruby 的用户
内存消耗 : 209.96 MB, 击败 12.50% 使用 Ruby 的用户
Scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| object Solution {
def merge(intervals: Array[Array[Int]]): Array[Array[Int]] = {
if (intervals.isEmpty) {
Array.empty[Array[Int]]
} else {
val sortedIntervals = intervals.sortBy(_.head)
var mergeArray = Array(sortedIntervals.head)
for (interval <- sortedIntervals.tail) {
val start = interval.head
val end = interval.last
if (start <= mergeArray.last.last) {
mergeArray = mergeArray.init :+ Array(mergeArray.last.head, end.max(mergeArray.last.last))
} else {
mergeArray :+= interval
}
}
mergeArray
}
}
}
|
结果
执行用时 : 702 ms, 击败 33.33% 使用 Scala 的用户
内存消耗 : 60.02 MB, 击败 83.33% 使用 Scala 的用户
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| impl Solution {
pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
if intervals.is_empty() {
return Vec::new();
}
let mut sorted_intervals = intervals.clone();
sorted_intervals.sort_by(|a, b| a[0].cmp(&b[0]));
let mut merged = vec![sorted_intervals[0].clone()];
for interval in sorted_intervals.iter().skip(1) {
let start = interval[0];
let end = interval[1];
if start <= merged.last().unwrap()[1] {
let last_merged = merged.last_mut().unwrap();
last_merged[1] = last_merged[1].max(end);
} else {
merged.push(interval.clone());
}
}
merged
}
}
|
结果
执行用时 : 7 ms, 击败 38.30% 使用 Rust 的用户
内存消耗 : 3.51 MB, 击败 5.68% 使用 Rust 的用户
Racket
暂时未解决
结果
执行用时 : ms, 击败 % 使用 Racket 的用户
内存消耗 : MB, 击败 % 使用 Racket 的用户
Erlang
暂时未解决
结果
执行用时 : ms, 击败 % 使用 Erlang 的用户
内存消耗 : MB, 击败 % 使用 Erlang 的用户
Elixir
暂时未解决
结果
执行用时 : ms, 击败 % 使用 Elixir 的用户
内存消耗 : MB, 击败 % 使用 Elixir 的用户