57.Insert Interval

tags: Medium,Array

57. Insert Interval

題目描述

You are given an array of non-overlapping intervals intervals where intervals[i] = [

$star{t}_i$,

$en{d}_i$] represent the start and the end of the i^th interval and intervals is sorted in ascending order by

$star{t}_i$. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by

$star{t}_i$ and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

範例

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

• 0 <= intervals.length <= 10⁴
• intervals[i].length == 2
• 0 <=
  $star{t}_i$ <=
  $en{d}_i$ <= 10⁵
• intervals is sorted by
  $star{t}_i$ in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 10⁵

解答

Javascript

function insert(intervals, newInterval) {
  const newIntervals = [];
  for (const interval of intervals) {
    if (interval[1] < newInterval[0]) {
      newIntervals.push(interval);
    } else if (interval[0] > newInterval[1]) {
      newIntervals.push(newInterval);
      newInterval = interval;
    } else {
      newInterval[0] = Math.min(interval[0], newInterval[0]);
      newInterval[1] = Math.max(interval[1], newInterval[1]);
    }
  }

  newIntervals.push(newInterval);

  return newIntervals;
}

Marsgoat Jan 16, 2023

function insert2(intervals, newInterval) {
  const newIntervals = [];
  for (const [start, end] of intervals) {
    const [newStart, newEnd] = newInterval;
    if (end < newStart) {
      newIntervals.push([start, end]);
    } else if (start > newEnd) {
      newIntervals.push(newInterval);
      newInterval = [start, end];
    } else {
      newInterval = [Math.min(start, newStart), Math.max(end, newEnd)];
    }
  }

  newIntervals.push(newInterval);

  return newIntervals;
}

function insert3(intervals, newInterval) {
  const newIntervals = [];
  const start = 0;
  const end = 1;
  for (const interval of intervals) {
    if (interval[end] < newInterval[start]) {
      newIntervals.push(interval);
    } else if (interval[start] > newInterval[end]) {
      newIntervals.push(newInterval);
      newInterval = interval;
    } else {
      newInterval[start] = Math.min(interval[start], newInterval[start]);
      newInterval[end] = Math.max(interval[end], newInterval[end]);
    }
  }

  newIntervals.push(newInterval);

  return newIntervals;
}

看到有人會把數字換成文字，不知道大家覺得2跟3哪個好，這樣可讀性真的有比較高嗎？
Marsgoat Jan 17, 2023

C++

思路:

1. 找到插入位置, 合併時, 區間起始取最小, 結束取最大

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int insert_start = newInterval[0], insert_end = newInterval[1];
        for(int i = 0; i < intervals.size(); i++)
        {
            auto& v = intervals[i];
            int cur_start = v[0], cur_end = v[1];
            if(insert_start > cur_end)
                res.push_back(v);
            else if(cur_start > insert_end)
            {
                res.push_back({insert_start, insert_end});
                while(i < intervals.size())
                {
                    res.push_back(intervals[i]);
                    i++;
                }
                return res;
            }
            else
            {
                insert_start = min(insert_start, cur_start);
                insert_end = max(insert_end, cur_end);
            }
        }
        res.push_back({insert_start, insert_end});
        return res;
    }
};

XD Jan 16, 2023

Time:

$O(n)$
Extra Space:

$O(n)$

Python

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        def does_intervals_overlap(a, b):
            return min(a[1], b[1]) - max(a[0], b[0]) >= 0

        def merge_intervals(a, b):
            return min(a[0], b[0]), max(a[1], b[1])

        isIntervalInserted = False
        for i, interval in enumerate(intervals):
            if newInterval[0] < interval[0]:
                index = i
                isIntervalInserted = True
                break

        if isIntervalInserted:
            intervals.insert(index, newInterval)
        else:
            intervals.append(newInterval)

        ans, i = [], 0
        while i < len(intervals):
            curr_interval = intervals[i]

            while i < len(intervals) and does_intervals_overlap(curr_interval, intervals[i]):
                curr_interval = merge_intervals(curr_interval, intervals[i])
                i += 1

            ans.append(curr_interval)

        return ans

Ron Chen Jan 17, 2023

Reference

回到題目列表