插入间隔Leetcode解决方案


难度级别 中等
经常问 亚马逊 Apple Facebook 谷歌 LinkedIn 微软 神谕 ServiceNow Twitter 尤伯杯
排列 DataMiner 排序

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

插入间隔Leetcode解决方案

使用案列

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

复杂度分析

时间复杂度

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

空间复杂度

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