57.插入区间

链接：57.插入区间
难度：Medium
标签：数组
简介：给出一个无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

题解 1 - javascript

• 编辑时间：2020-11-04
• 执行用时：96ms
• 内存消耗：42.7MB
• 编程语言：javascript
• 解法介绍：遍历一遍进行合并数组，并校验是否已插入。

function insert(intervals: number[][], newInterval: number[]): number[][] {
  let [newStart, newEnd] = newInterval;
  const ans: number[][] = [];
  let inserted = false;
  for (const interval of intervals) {
    const [start, end] = interval;
    if (inserted) {
      ans.push(interval);
    } else if (start > newEnd) {
      ans.push([newStart, newEnd]);
      ans.push(interval);
      inserted = true;
    } else if (end < newStart) {
      ans.push(interval);
    } else if (start <= newStart && end >= newEnd) {
      ans.push(interval);
      inserted = true;
    } else {
      newStart = Math.min(start, newStart);
      newEnd = Math.max(end, newEnd);
    }
  }
  inserted || ans.push([newStart, newEnd]);
  return ans;
}

题解 2 - cpp

• 编辑时间：2023-08-28
• 执行用时：16ms
• 内存消耗：16.22MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size(), i = 0;
        while (i < n && intervals[i][1] < newInterval[0]) {
            res.push_back(intervals[i]);
            i += 1;
        }
        if (i == n) {
            res.push_back(newInterval);
        } else if (intervals[i][0] > newInterval[1]) {
            res.push_back(newInterval);
            while (i < n) {
                res.push_back(intervals[i]);
                i += 1;
            }
        } else {
            res.push_back(
                vector<int>{
                    min(intervals[i][0], newInterval[0]),
                    max(intervals[i][1], newInterval[1])
                }
            );
            i += 1;
            while (i < n) {
                if (res.back()[1] >= intervals[i][0]) {
                    res.back()[1] = max(res.back()[1], intervals[i][1]);
                } else {
                    res.push_back(intervals[i]);
                }
                i += 1;
            }
        }
        return res;
    }
};

题解 3 - python

• 编辑时间：2023-08-28
• 执行用时：60ms
• 内存消耗：17.75MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        n = len(intervals)
        i = 0
        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1
        if i == n:
            res.append(newInterval)
        elif intervals[i][0] > newInterval[1]:
            res.append(newInterval)
            while i < n:
                res.append(intervals[i])
                i += 1
        else:
            res.append(
                [min(intervals[i][0], newInterval[0]),
                    max(intervals[i][1], newInterval[1])]
            )
            i += 1
            while i < n:
                if res[-1][1] >= intervals[i][0]:
                    res[-1][1] = max(res[-1][1], intervals[i][1])
                else:
                    res.append(intervals[i])
                i += 1
        return res

题解 4 - rust

• 编辑时间：2023-08-28
• 内存消耗：2.54MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn insert(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> {
        use std::cmp::{max, min};
        let mut res = vec![];
        let n = intervals.len();
        let mut i = 0;
        while i < n && intervals[i][1] < new_interval[0] {
            res.push(intervals[i].clone());
            i += 1;
        }
        if i == n {
            res.push(new_interval);
        } else if intervals[i][0] > new_interval[1] {
            res.push(new_interval);
            while i < n {
                res.push(intervals[i].clone());
                i += 1;
            }
        } else {
            res.push(vec![
                min(intervals[i][0], new_interval[0]),
                max(intervals[i][1], new_interval[1]),
            ]);
            i += 1;
            while i < n {
                if res.last().unwrap()[1] >= intervals[i][0] {
                    res.last_mut().unwrap()[1] = max(res.last().unwrap()[1], intervals[i][1]);
                } else {
                    res.push(intervals[i].clone());
                }
                i += 1;
            }
        }
        res
    }
}