Устаўце інтэрвал рашэння Leetcode  


Узровень складанасці серада
Часта пытаюцца ў амазонка яблык facebook Google LinkedIn Microsoft Аракул ServiceNow Twitter Uber
алгарытмы масіў кадаваньне Dataminr інтэрв'ю інтэрв'юп LeetCode LeetCodeSolutions Род

Праблема Insert Interval Leetcode Solution дае нам спіс некаторых інтэрвалаў і адзін асобны інтэрвал. Тады нам кажуць уставіць гэты новы інтэрвал сярод спісу інтэрвалаў. Такім чынам, новы інтэрвал можа перасякацца з інтэрваламі, якія ўжо ёсць у спісе, а можа і не. У выпадку перасячэння мы зліваем інтэрвалы. У адваротным выпадку мы проста ўстаўляем у пазіцыю, калі яна ідзе па ўзрастанні спісу інтэрвалаў.

Устаўце інтэрвал рашэння LeetcodePin

Прыклад  

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

Тлумачэнне: Новы інтэрвал перасякаецца з першым інтэрвалам у спісе. Такім чынам, новы інтэрвал аб'ядноўваецца з першым інтэрвалам. І вось як нам застаецца дадзены выхад.

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

Тлумачэнне: Першапачаткова, бо ў спісе не было прамежкаў. Мы проста ўставілі новы інтэрвал.

Падыход да ўстаўкі інтэрвальнага рашэння з выкарыстаннем штрыхкода  

Праблема Insert Interval Leetcode Solution дала нам некаторыя інтэрвалы і дадатковы інтэрвал, які неабходна ўставіць. Такім чынам, мы можам вырашыць праблему, калі зможам змадэляваць магчымасці, якія могуць узнікнуць. Ёсць дзве магчымасці: альбо новы інтэрвал перасякаецца з некаторымі інтэрваламі, якія ўжо ёсць у спісе, альбо не. Такім чынам, калі гэта адбываецца, мы проста зліваем іх, інакш размяшчаем інтэрвал у пэўным становішчы. Пад канкрэтным становішчам мы маем на ўвазе, што парадак узрастання ў спісе захоўваецца нават пасля ўстаўкі.

Глядзіце таксама
Мінімальны час, неабходны для гніення ўсіх апельсінаў

Такім чынам, для гэтага мы ствараем новы вектар (масіў) вектараў. Мы пачынаем ўстаўляць інтэрвалы ў гэты нядаўна створаны вектар вываду. Мы правяраем, ці перакрываецца бягучы інтэрвал з інтэрвалам, які трэба ўставіць. Калі яны гэта робяць, мы вырываемся з цыкла. Пасля цыкла мы правяраем, ці ёсць элемент, які перакрываецца, сярод інтэрвалаў, прысутных у спісе. Калі яны перакрываюцца, мы аб'ядноўваем бягучы інтэрвал з новым і ўстаўляем астатнія інтэрвалы. Але калі яны гэтага не робяць, мы ўстаўляем элементы ў выходны вектар, пакуль зыходнае становішча інтэрвала не стане меншым за пачатковае становішча інтэрвала, які трэба ўставіць. Затым мы проста ўстаўляем новы інтэрвал, а потым астатнія інтэрвалы.

код  

Код C ++ для ўстаўкі інтэрвала 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-код для ўстаўкі інтэрвальнага рашэння Leetcode

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

Аналіз складанасці  

Складанасць часу

O (N), таму што мы проста прайшлі па спісе і ўставілі інтэрвалы ў выходны вектар. Такім чынам, усе гэтыя аперацыі займаюць лінейны час.

Глядзіце таксама
Мінімальная адлегласць паміж вузламі BST Рашэнне Leetcode

Касмічная складанасць

O (N), таму што мы стварылі новы вектар вектараў, які захоўвае N альбо N + 1 элементы. Складанасць касмічнай прасторы таксама лінейная.

1