अन्तराल लीटकोड समाधान सम्मिलित गर्नुहोस्


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन एप्पल फेसबुक गुगल LinkedIn माइक्रोसफ्ट बजेट अब सेवा twitter Uber
एरे डाटामिनर सर्ट

समस्या घुसाउनुहोस् अन्तराल लीटकोड समाधानले हामीलाई केही अन्तरालहरूको सूची र एक छुट्टै अन्तराल प्रदान गर्दछ। त्यसपछि हामीलाई अन्तरालहरूको सूची बीचमा यो नयाँ अन्तराल सम्मिलित गर्न भनियो। त्यसो भए नयाँ अन्तराल अन्तरालसँग मिल्दो छ जुन सूचिमा पहिले नै रहेको छ, वा हुन सक्दैन। यदि त्यहाँ कुनै छेदन छ हामी अन्तरालहरू मर्ज गर्दछौं। अन्यथा, हामी केवल एक स्थितिमा सम्मिलित गर्दछौं जहाँ यो अन्तरालहरूको सूचीको आरोही क्रमको अनुसरण गर्दछ।

अन्तराल लीटकोड समाधान सम्मिलित गर्नुहोस्

उदाहरणका

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

स्पष्टीकरण: नयाँ अन्तराल सूचीको पहिलो अन्तरालसँग मिल्छ। त्यसो भए नयाँ अन्तराल पहिलो अन्तरालसँग मर्ज गरियो। र यसरी हामी दिईएको आउटपुट बाँकी छौं।

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

स्पष्टीकरण: सुरूमा, किनकि सूचीमा कुनै अन्तरालहरू थिएनन्। हामीले केवल नयाँ अन्तराल सम्मिलित गर्‍यौं।

सम्मिलित अन्तराल लीटकोड समाधानको लागि दृष्टिकोण

समस्या घुसाउनुहोस् अन्तराल लीटकोड समाधानले हामीलाई केही अन्तरालहरू प्रदान गर्दछ र थप अन्तराल जुन घुसाउनु पर्छ। त्यसो भए, हामी समस्या सुल्झाउन सक्छौं यदि हामी उत्पन्न हुन सक्ने सम्भावाहरू अनुकरण गर्न सक्छौं। त्यहाँ दुई सम्भाव्यता छन्, या त नयाँ अन्तराल कालान्तर मा अन्तराल संगै केही पहिले नै सूची मा उपस्थित छ वा छैन। त्यसो भए, यदि हामी यस्तो गर्छौं भने, हामी केवल तिनीहरूलाई मर्ज गर्दछौं अन्यत्र हामी अन्तराल एक विशेष स्थानमा राख्छौं। विशिष्ट स्थितिबाट, हाम्रो मतलव सूचीमा आरोहण अर्डर सम्मिलन पछि पनि कायम गरीन्छ।

त्यसो भए, यसलाई ह्यान्डल गर्न हामी नयाँ भेक्टर बनाउँछौं (array) भेक्टरहरूको। हामी नयाँ सिर्जना गरिएको आउटपुट भेक्टरमा अन्तरालहरू घुसाउन थाल्छौं। हामी जाँच गर्दछौं यदि हालको मध्यान्तर मध्यान्तरमा मध्यान्तर संग मिल्छ भने। यदि ती गरेमा, हामी लूपबाट बाहिर निस्कन्छौं। लूप पछाडि, हामी जाँच गर्छौं कि एलिभरेन्ट एलिमेन्ट सूचीमा उपस्थित अन्तरालहरू बीच छ वा छैन। यदि उनीहरू ओभरल्याप हुन्छन्, हामी हालको अन्तराललाई नयाँ अन्तरालसँग मर्ज गर्दछौं र बाँकी अन्तरालहरू सम्मिलित गर्दछौं। तर यदि ती गर्दैन भने, तब हामी अन्तर्निर्देशको भेक्टरमा एलिमेन्टहरू सम्मिलित गर्दछौं जबसम्म इन्टरलको शुरुवात स्थिति इन्टरल हुने शुरुवात भन्दा कम सम्म सम्मिलित हुन जान्छ। त्यसपछि हामी केवल नयाँ अन्तराल सम्मिलित गर्छौं र त्यसपछि अन्तरालहरू बाँकी हुन्छ।

कोड

C ++ कोड सम्मिलित अन्तराल लीटकोड समाधानको लागि

#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

जटिलता विश्लेषण

समय जटिलता

O (N), किनकि हामीले केवल सूचीमा पार गर्यौं र अन्तरालहरू आउटपुट भेक्टरमा सम्मिलित गर्यौं। त्यसो भए, यी सबै अपरेसनहरू रेखात्मक समय लिन्छन्।

ठाउँ जटिलता

O (N), किनकि हामीले भेक्टरहरूको नयाँ भेक्टर सिर्जना गरेका छौं जसले N वा N + १ तत्त्वहरू भण्डार गर्दछ। ठाउँ जटिलता पनि रैखिक छ।