ఇంటర్వెల్ లీట్‌కోడ్ పరిష్కారాన్ని చొప్పించండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ లింక్డ్ఇన్ మైక్రోసాఫ్ట్ ఒరాకిల్ ServiceNow <span style="font-family: Mandali; ">ట్విట్టర్</span> ఉబెర్
అర్రే డాటామిన్ర్ క్రమీకరించు

ఇన్సర్ట్ ఇంటర్వెల్ లీట్‌కోడ్ సొల్యూషన్ సమస్య మాకు కొన్ని విరామాల జాబితాను మరియు ఒక ప్రత్యేక విరామాన్ని అందిస్తుంది. ఈ కొత్త విరామాన్ని విరామాల జాబితాలో చేర్చమని మాకు చెప్పబడింది. కాబట్టి, క్రొత్త విరామం ఇప్పటికే జాబితాలో ఉన్న విరామాలతో కలుస్తుంది లేదా కాకపోవచ్చు. ఒక ఖండన ఉన్నట్లయితే మేము విరామాలను విలీనం చేస్తాము. లేకపోతే, మేము విరామాల జాబితా యొక్క ఆరోహణ క్రమాన్ని అనుసరించే స్థితిలో చొప్పించాము.

ఇంటర్వెల్ లీట్‌కోడ్ పరిష్కారాన్ని చొప్పించండి

ఉదాహరణ

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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), ఎందుకంటే మేము జాబితాలో ప్రయాణించి, విరామాలను అవుట్పుట్ వెక్టర్‌లోకి చేర్చాము. కాబట్టి, ఈ కార్యకలాపాలన్నీ సరళ సమయం తీసుకుంటాయి.

అంతరిక్ష సంక్లిష్టత

పై), ఎందుకంటే మేము N లేదా N + 1 మూలకాలను నిల్వ చేసే వెక్టర్స్ యొక్క కొత్త వెక్టర్‌ను సృష్టించాము. స్థల సంక్లిష్టత కూడా సరళంగా ఉంటుంది.