力扣00057.插入区间

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 8 分钟
插入区间、数组、中等

题目描述

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

示例 3：

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

示例 4：

输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]

示例 5：

输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]

提示：

  • $0 <= intervals.length <= 10^4$
  • intervals[i].length == 2
  • $0 <= intervals[i][0] <= intervals[i][1] <= 10^5$
  • intervals 根据 intervals[i][0] 按 升序 排列
  • newInterval.length == 2
  • $0 <= newInterval[0] <= newInterval[1] <= 10^5$

解决方法

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>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        int i = 0;
        while (i < intervals.size() && intervals[i][1] < newInterval[0]) {
            result.push_back(intervals[i]);
            i++;
        }
        while (i < intervals.size() && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.push_back(newInterval);
        while (i < intervals.size()) {
            result.push_back(intervals[i]);
            i++;
        }
        return result;
    }
};

结果

执行用时 : 10 ms, 击败 83.58% 使用 C++ 的用户

内存消耗 : 19.94 MB, 击败 34.44% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }
        return result.toArray(new int[result.size()][]);
    }
}

结果

执行用时 : 1 ms, 击败 96.15% 使用 Java 的用户

内存消耗 : 43.74 MB, 击败 44.16% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        result = []
        i = 0
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)
        while i < len(intervals):
            result.append(intervals[i])
            i += 1
        return result

结果

执行用时 : 20 ms, 击败 75.85% 使用 Python 的用户

内存消耗 : 13.05 MB, 击败 81.10% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        i = 0
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)
        while i < len(intervals):
            result.append(intervals[i])
            i += 1
        return result

结果

执行用时 : 51 ms, 击败 20.89% 使用 Python3 的用户

内存消耗 : 18.55 MB, 击败 50.93% 使用 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
45
46
47
48
49
50
51
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    int left = newInterval[0];
    int right = newInterval[1];
    bool placed = false;
    int** ans = malloc(sizeof(int*) * (intervalsSize + 1));
    *returnColumnSizes = malloc(sizeof(int) * (intervalsSize + 1));
    for (int i = 0; i < intervalsSize; ++i) {
        int* interval = intervals[i];
        if (interval[0] > right) {
            if (!placed) {
                int* tmp = malloc(sizeof(int) * 2);
                tmp[0] = left, tmp[1] = right;
                (*returnColumnSizes)[*returnSize] = 2;
                ans[(*returnSize)++] = tmp;
                placed = true;
            }
            int* tmp = malloc(sizeof(int) * 2);
            memcpy(tmp, interval, sizeof(int) * 2);
            (*returnColumnSizes)[*returnSize] = 2;
            ans[(*returnSize)++] = tmp;
        } else if (interval[1] < left) {
            int* tmp = malloc(sizeof(int) * 2);
            memcpy(tmp, interval, sizeof(int) * 2);
            (*returnColumnSizes)[*returnSize] = 2;
            ans[(*returnSize)++] = tmp;
        } else {
            left = fmin(left, interval[0]);
            right = fmax(right, interval[1]);
        }
    }
    if (!placed) {
        int* tmp = malloc(sizeof(int) * 2);
        tmp[0] = left, tmp[1] = right;
        (*returnColumnSizes)[*returnSize] = 2;
        ans[(*returnSize)++] = tmp;
    }
    return ans;
}
void freeMemory(int** intervals, int returnSize, int* returnColumnSizes) {
    for (int i = 0; i < returnSize; i++) {
        free(intervals[i]);
    }
    free(intervals);
    free(returnColumnSizes);
}

结果

执行用时 : 13 ms, 击败 69.23% 使用 C 的用户

内存消耗 : 7.73 MB, 击败 93.01% 使用 C 的用户

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
public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new List<int[]>();
        int left = newInterval[0];
        int right = newInterval[1];
        bool placed = false;
        foreach (int[] interval in intervals) {
            if (interval[1] < left) {
                result.Add(interval);
            } else if (interval[0] > right) {
                if (!placed) {
                    result.Add(new int[] { left, right });
                    placed = true;
                }
                result.Add(interval);
            } else {
                left = Math.Min(left, interval[0]);
                right = Math.Max(right, interval[1]);
            }
        }
        if (!placed) {
            result.Add(new int[] { left, right });
        }
        return result.ToArray();
    }
}

结果

执行用时 : 125 ms, 击败 55.91% 使用 C# 的用户

内存消耗 : 49.94 MB, 击败 16.13% 使用 C# 的用户

JavaScript

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
/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
    let result = [];
    let left = newInterval[0];
    let right = newInterval[1];
    let placed = false;
    for (let interval of intervals) {
        if (interval[1] < left) {
            result.push(interval);
        } else if (interval[0] > right) {
            if (!placed) {
                result.push([left, right]);
                placed = true;
            }
            result.push(interval);
        } else {
            left = Math.min(left, interval[0]);
            right = Math.max(right, interval[1]);
        }
    }
    if (!placed) {
        result.push([left, right]);
    }
    return result;
};

结果

执行用时 : 71 ms, 击败 72.40% 使用 JavaScript 的用户

内存消耗 : 52.78 MB, 击败 14.99% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function insert(intervals: number[][], newInterval: number[]): number[][] {
    let result: number[][] = [];
    let left: number = newInterval[0];
    let right: number = newInterval[1];
    let placed: boolean = false;
    for (let interval of intervals) {
        if (interval[1] < left) {
            result.push(interval);
        } else if (interval[0] > right) {
            if (!placed) {
                result.push([left, right]);
                placed = true;
            }
            result.push(interval);
        } else {
            left = Math.min(left, interval[0]);
            right = Math.max(right, interval[1]);
        }
    }
    if (!placed) {
        result.push([left, right]);
    }
    return result;
}

结果

执行用时 : 80 ms, 击败 52.83% 使用 TypeScript 的用户

内存消耗 : 54.35 MB, 击败 13.21% 使用 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
26
27
28
29
30
31
32
class Solution {

    /**
     * @param Integer[][] $intervals
     * @param Integer[] $newInterval
     * @return Integer[][]
     */
    function insert($intervals, $newInterval) {
        $result = [];
        $left = $newInterval[0];
        $right = $newInterval[1];
        $placed = false;
        foreach ($intervals as $interval) {
            if ($interval[1] < $left) {
                $result[] = $interval;
            } else if ($interval[0] > $right) {
                if (!$placed) {
                    $result[] = [$left, $right];
                    $placed = true;
                }
                $result[] = $interval;
            } else {
                $left = min($left, $interval[0]);
                $right = max($right, $interval[1]);
            }
        }
        if (!$placed) {
            $result[] = [$left, $right];
        }
        return $result;
    }
}

结果

执行用时 : 23 ms, 击败 54.55% 使用 PHP 的用户

内存消耗 : 24.38 MB, 击败 72.73% 使用 PHP 的用户

Swift

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
class Solution {
    func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        var left = newInterval[0]
        var right = newInterval[1]
        var placed = false
        for interval in intervals {
            if interval[1] < left {
                result.append(interval)
            } else if interval[0] > right {
                if !placed {
                    result.append([left, right])
                    placed = true
                }
                result.append(interval)
            } else {
                left = min(left, interval[0])
                right = max(right, interval[1])
            }
        }
        if !placed {
            result.append([left, right])
        }
        return result
    }
}

结果

执行用时 : 33 ms, 击败 77.55% 使用 Swift 的用户

内存消耗 : 16.31 MB, 击败 16.33% 使用 Swift 的用户

Kotlin

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
class Solution {
    fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
        val result = mutableListOf<IntArray>()
        var left = newInterval[0]
        var right = newInterval[1]
        var placed = false
        for (interval in intervals) {
            if (interval[1] < left) {
                result.add(interval)
            } else if (interval[0] > right) {
                if (!placed) {
                    result.add(intArrayOf(left, right))
                    placed = true
                }
                result.add(interval)
            } else {
                left = left.coerceAtMost(interval[0])
                right = right.coerceAtLeast(interval[1])
            }
        }
        if (!placed) {
            result.add(intArrayOf(left, right))
        }
        return result.toTypedArray()
    }
}

结果

执行用时 : 237 ms, 击败 62.50% 使用 Kotlin 的用户

内存消耗 : 42.70 MB, 击败 8.33% 使用 Kotlin 的用户

Dart

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
class Solution {
  List<List<int>> insert(List<List<int>> intervals, List<int> newInterval) {
    List<List<int>> result = [];
    int left = newInterval[0];
    int right = newInterval[1];
    bool placed = false;
    for (List<int> interval in intervals) {
        if (interval[1] < left) {
        result.add(interval);
        } else if (interval[0] > right) {
        if (!placed) {
            result.add([left, right]);
            placed = true;
        }
        result.add(interval);
        } else {
        left = left < interval[0] ? left : interval[0];
        right = right > interval[1] ? right : interval[1];
        }
    }
    if (!placed) {
        result.add([left, right]);
    }
    return result;
    }
}

结果

执行用时 : 337 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 145.83 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
25
26
27
28
29
30
31
32
33
34
35
func insert(intervals [][]int, newInterval []int) [][]int {
	result := make([][]int, 0)
	left, right := newInterval[0], newInterval[1]
	placed := false
	for _, interval := range intervals {
		if interval[1] < left {
			result = append(result, interval)
		} else if interval[0] > right {
			if !placed {
				result = append(result, []int{left, right})
				placed = true
			}
			result = append(result, interval)
		} else {
			left = min(left, interval[0])
			right = max(right, interval[1])
		}
	}
	if !placed {
		result = append(result, []int{left, right})
	}
	return result
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

结果

执行用时 : 7 ms, 击败 31.86% 使用 Go 的用户

内存消耗 : 4.20 MB, 击败 33.05% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# @param {Integer[][]} intervals
# @param {Integer[]} new_interval
# @return {Integer[][]}
def insert(intervals, new_interval)
  result = []
  left, right = new_interval[0], new_interval[1]
  placed = false
  intervals.each do |interval|
    if interval[1] < left
      result << interval
    elsif interval[0] > right
      unless placed
        result << [left, right]
        placed = true
      end
      result << interval
    else
      left = [left, interval[0]].min
      right = [right, interval[1]].max
    end
  end
  result << [left, right] unless placed
  result
end

结果

执行用时 : 68 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.96 MB, 击败 50.00% 使用 Ruby 的用户

Scala

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
object Solution {
  def insert(intervals: Array[Array[Int]], newInterval: Array[Int]): Array[Array[Int]] = {
    var result: List[Array[Int]] = List()
    var left = newInterval(0)
    var right = newInterval(1)
    var placed = false
    for (interval <- intervals) {
      if (interval(1) < left) {
        result :+= interval
      } else if (interval(0) > right) {
        if (!placed) {
          result :+= Array(left, right)
          placed = true
        }
        result :+= interval
      } else {
        left = left min interval(0)
        right = right max interval(1)
      }
    }
    if (!placed) {
      result :+= Array(left, right)
    }
    result.toArray
  }
}

结果

执行用时 : 540 ms, 击败 77.78% 使用 Scala 的用户

内存消耗 : 57.64 MB, 击败 88.89% 使用 Scala 的用户

Rust

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
impl Solution {
    pub fn insert(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        let mut left = new_interval[0];
        let mut right = new_interval[1];
        let mut placed = false;
        for interval in intervals {
            if interval[1] < left {
                result.push(interval);
            } else if interval[0] > right {
                if !placed {
                    result.push(vec![left, right]);
                    placed = true;
                }
                result.push(interval);
            } else {
                left = left.min(interval[0]);
                right = right.max(interval[1]);
            }
        }
        if !placed {
            result.push(vec![left, right]);
        }
        result
    }
}

结果

执行用时 : 2 ms, 击败 50.00% 使用 Rust 的用户

内存消耗 : 2.64 MB, 击败 40.32% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户