अंतराल लीटकोड सोल्यूशन घाला


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन सफरचंद फेसबुक Google संलग्न मायक्रोसॉफ्ट ओरॅकल सेवा ट्विटर उबेर
अरे डेटामिनर क्रमवारी लावा

इन्सर्ट इंटरवल लीटकोड सोल्यूशन आम्हाला काही अंतराची यादी आणि एक वेगळा मध्यांतर प्रदान करते. नंतर आपल्याला अंतराच्या यादीमध्ये हा नवीन मध्यांतर घालायला सांगितले जाते. तर, नवीन मध्यांतर कदाचित सूचीमध्ये आधीपासूनच असलेल्या अंतराळ्यांसह प्रतिच्छेदन करत असेल किंवा कदाचित नाही. जर एखादा छेदनबिंदू असेल तर आम्ही मध्यांतर विलीन करू. अन्यथा, आम्ही सहजपणे अशा स्थानावर अंतर्भूत करतो जिथे ते अंतराच्या सूचीच्या चढत्या क्रमाचे अनुसरण करते.

अंतराल लीटकोड सोल्यूशन घाला

उदाहरण

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 घटक संचयित करणारे वेक्टरचे नवीन वेक्टर तयार केले आहे. जागेची जटिलता देखील रेषात्मक आहे.