Уметните Интервал Леетцоде решење


Ниво тешкоће Средњи
Често питани у амазонка јабука фацебоок гоогле ЛинкедИн мицрософт пророчанство СервицеНов твиттер Убер
Ред Датаминр Врста

Проблем Инсерт Интервал Леетцоде Солутион пружа нам листу неких интервала и један одвојени интервал. Тада нам је речено да овај нови интервал убацимо на листу интервала. Дакле, нови интервал се можда пресијеца с интервалима који су већ на листи или не. У случају да постоји пресек, спајамо интервале. У супротном, једноставно уметнемо на место где следи узлазни редослед листе интервала.

Уметните Интервал Леетцоде решење

Пример

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

Објашњење: Нови интервал укршта се са првим интервалом на листи. Дакле, нови интервал се спаја са првим интервалом. И тако нам остаје дати излаз.

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

Објашњење: У почетку, будући да на листи није било интервала. Једноставно смо убацили нови интервал.

Приступ решењу уметања интервалног кода

Проблем Инсерт Интервал Леетцоде Солутион пружио нам је неке интервале и додатни интервал који треба уметнути. Дакле, проблем можемо решити ако симулирамо могућности које се могу појавити. Постоје две могућности, или се нови интервал пресеца са неким интервалима који су већ присутни на листи, или не. Дакле, ако се догоди, једноставно их спојимо, а други интервал постављамо на одређену позицију. Под одређеним положајем подразумевамо да се растући поредак на листи одржава и након уметања.

Дакле, да бисмо то решили, креирамо нови вектор (поредак) вектора. Почињемо да убацујемо интервале у овај новостворени излазни вектор. Проверавамо да ли се тренутни интервал преклапа са интервалом који треба уметнути. Ако то учине, онда ћемо побећи из петље. После петље проверавамо да ли је елемент који се преклапа међу интервалима присутним на листи. Ако се преклапају, тренутни интервал спојимо са новим и убацимо остатак интервала. Али ако не, убацимо елементе у излазни вектор све док почетна позиција интервала не буде мања од почетне позиције интервала који треба уметнути. Тада једноставно убацимо нови интервал, а затим остатак интервала.

код

Ц ++ код за Инсерт Интервал Леетцоде Солутион

#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

Јава код за Инсерт Интервал Леетцоде Солутион

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

Анализа сложености

Сложеност времена

НА), јер смо једноставно прешли преко листе и уметнули интервале у излазни вектор. Дакле, све ове операције требају линеарно време.

Сложеност простора

НА), јер смо створили нови вектор вектора који чува Н или Н + 1 елементе. Сложеност простора је такође линеарна.