Вмъкнете Interval Leetcode Solution  


Ниво на трудност M
Често задавани в Амазонка ябълка Facebook Google LinkedIn Microsoft Оракул ServiceNow кикотене Uber
алгоритми Array кодиране Dataminr Интервю интерпретация LeetCode LeetCodeSolutions Вид

Проблемът Insert Interval Leetcode Solution ни предоставя списък с някои интервали и един отделен интервал. След това ни се казва да вмъкнем този нов интервал сред списъка с интервали. Така че, новият интервал може да се пресича с интервали, които вече са в списъка, или не. В случай, че има пресичане, обединяваме интервалите. В противен случай просто вмъкваме на място, където следва възходящия ред на списъка с интервали.

Вмъкнете Interval Leetcode Solution

Пример  

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

Обяснение: Новият интервал се пресича с първия интервал в списъка. Така че новият интервал се обединява с първия интервал. И така ни остава дадения изход.

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

Обяснение: Първоначално, тъй като в списъка няма интервали. Просто вмъкнахме новия интервал.

Подход за Insert Interval Leetcode Solution  

Проблемът Insert Interval Leetcode Solution ни предостави някои интервали и допълнителен интервал, който трябва да бъде вмъкнат. И така, можем да разрешим проблема, ако можем да симулираме възможностите, които могат да възникнат. Има две възможности, или новият интервал се пресича с някои интервали, които вече присъстват в списъка, или не. Така че, ако се случи, ние просто ги обединяваме, иначе поставяме интервала на определена позиция. Под конкретна позиция имаме предвид, че възходящият ред в списъка се поддържа дори след вмъкването.

Вижте също
Минимално време, необходимо за гниене на всички портокали

Така че, за да се справим с това, ние създаваме нов вектор (масив) на вектори. Започваме да вмъкваме интервалите в този новосъздаден изходен вектор. Проверяваме дали текущият интервал се припокрива с интервала, който трябва да се вмъкне. Ако го направят, тогава излизаме от цикъла. След цикъла проверяваме дали елементът, който се припокрива, е сред интервалите, присъстващи в списъка. Ако те се припокриват, ние обединяваме текущия интервал с новия интервал и вмъкваме останалите интервали. Но ако не го направят, тогава ние вмъкваме елементите в изходния вектор, докато началната позиция на интервала не е по-малка от началната позиция на интервала, който трябва да се вмъкне. След това просто вмъкваме новия интервал и след това останалите интервали.

код  

C ++ код за Insert Interval Leetcode Solution

#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

Java код за Insert Interval Leetcode Solution

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 елементи. Сложността на пространството също е линейна.