插入间隔Leetcode解决方案  


难度级别 中等
经常问 亚马逊 Apple Facebook 谷歌 LinkedIn 微软 神谕 ServiceNow Twitter 尤伯杯
算法 排列 编码 DataMiner 访谈 面试准备 力码 力码解决方案 排序

问题插入间隔Leetcode解决方案为我们提供了一些间隔列表和一个单独的间隔列表。 然后,我们被告知在间隔列表中插入这个新间隔。 因此,新间隔可能与列表中已经存在的间隔相交,也可能不相交。 如果有交叉点,我们将合并区间。 否则,我们只需在遵循间隔列表的升序的位置插入即可。

插入间隔Leetcode解决方案Pin

使用案列  

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

说明:新间隔与列表中的第一个间隔相交。 因此,新间隔将与第一个间隔合并。 这就是给定输出的方式。

intervals = [], newInterval = [0,5]
[0,5]

说明:最初,因为列表中没有间隔。 我们只是插入了新间隔。

插入间隔Leetcode解决方案的方法  

问题插入间隔Leetcode解决方案为我们提供了一些间隔和一个需要插入的额外间隔。 因此,如果我们可以模拟可能出现的可能性,则可以解决该问题。 有两种可能性,要么新间隔与列表中已经存在的某些间隔相交,要么不相交。 因此,如果确实如此,我们将简单地合并它们,否则我们将间隔放置在特定位置。 通过特定位置,我们的意思是即使插入后列表中的升序也保持不变。

参见
腐烂所有橘子所需的最短时间

因此,为了解决这个问题,我们创建了一个新的向量(排列)的向量。 我们开始将间隔插入到这个新创建的输出向量中。 我们检查当前间隔是否与要插入的间隔重叠。 如果他们这样做,那么我们就跳出了循环。 循环之后,我们检查重叠的元素是否在列表中存在的间隔之中。 如果它们重叠,则将当前间隔与新间隔合并,然后插入其余间隔。 但是,如果没有,则我们将元素插入到输出向量中,直到间隔的开始位置小于要插入的间隔的开始位置为止。 然后,我们只需插入新间隔,然后插入其余间隔。

代码  

插入间隔Leetcode解决方案的C ++代码

#include <bits/stdc++.h>
using namespace std;

bool overlap(vector<int> a, vector<int> b){
    return (a[0] <= b[0] && b[0] <= a[1]) || (b[0] <= a[0] && a[0] <= b[1]);
}

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    int i;
    vector<vector<int>> newIntervals;
    for(i=0;i<intervals.size();i++)
        if(overlap(intervals[i], newInterval))
            break;
        else
            newIntervals.push_back(intervals[i]);
    if(i<intervals.size()){
        intervals[i][0] = min(intervals[i][0], newInterval[0]);
        intervals[i][1] = max(intervals[i][1], newInterval[1]);
        newIntervals.push_back(intervals[i]);
        int j = i;
        i++;
        for(;i<intervals.size();i++)
            if(overlap(intervals[j], intervals[i])){
                newIntervals[j][0] = min(newIntervals[j][0], intervals[i][0]);
                newIntervals[j][1] = max(newIntervals[j][1], intervals[i][1]);
            } else
                newIntervals.push_back(intervals[i]);
        return newIntervals;
    }
    for(i=0;i<intervals.size();i++)
        if(newIntervals[i][0]>newInterval[0])
            break;
    newIntervals.insert(newIntervals.begin() + i, newInterval);
    return newIntervals;
}

int main(){
  vector<vector<int>> intervals = {{0,5}};
  vector<int> newInterval = {1,6};
  vector<vector<int>> output = insert(intervals, newInterval);
  for(int i=0;i<output.size();i++)
    cout<<output[i][0]<<" "<<output[i][1];
}
0 6

用于插入间隔Leetcode解决方案的Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
  
    private static boolean overlap(int[] a, int[] b){
        return (a[0] <= b[0] && b[0] <= a[1]) || (b[0] <= a[0] && a[0] <= b[1]);
    }
    
    private static int[][] insert(int[][] intervals, int[] newInterval) {
        int i;
        ArrayList<Integer[]> newIntervals = new ArrayList<Integer[]>();
        for(i=0;i<intervals.length;i++)
            if(overlap(intervals[i], newInterval))
                break;
            else
                newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
        if(i<intervals.length){
            intervals[i][0] = Math.min(intervals[i][0], newInterval[0]);
            intervals[i][1] = Math.max(intervals[i][1], newInterval[1]);
            newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
            int j = i;
            i++;
            for(;i<intervals.length;i++)
                if(overlap(intervals[j], intervals[i])){
                    int a = Math.min(intervals[j][0], intervals[i][0]);
                    int b = Math.max(intervals[j][1], intervals[i][1]);
                    newIntervals.set(j, new Integer[]{a, b});
                } else
                    newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
            int[][] to_return = new int[newIntervals.size()][2];
            for(i=0;i<to_return.length;i++){
                to_return[i][0] = newIntervals.get(i)[0];
                to_return[i][1] = newIntervals.get(i)[1];
            }
            return to_return;
        }
        for(i=0;i<intervals.length;i++)
            if(newIntervals.get(i)[0]>newInterval[0])
                break;
        
        newIntervals.add(i, new Integer[]{newInterval[0], newInterval[1]});
        
        int[][] to_return = new int[newIntervals.size()][2];
            for(i=0;i<to_return.length;i++){
                to_return[i][0] = newIntervals.get(i)[0];
                to_return[i][1] = newIntervals.get(i)[1];
            }
        return to_return;
    }
    
    public static void main (String[] args) throws java.lang.Exception {
    int[][] intervals = {{0,5}};
    int[] newInterval = {1,6};
    int[][] output = insert(intervals, newInterval);
    for(int i=0;i<intervals.length;i++)
      System.out.print(output[i][0] + " " + output[i][1]);
  }
}
0 6

复杂度分析  

时间复杂度

上), 因为我们只是遍历了列表,然后将间隔插入了输出向量。 因此,所有这些操作都需要线性时间。

参见
BST节点之间的最小距离Leetcode解决方案

空间复杂度

上), 因为我们创建了一个新的向量向量来存储N或N + 1个元素。 空间复杂度也是线性的。

1