অন্তর্বর্তী লেটকোড সমাধান sertোকান


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক আপেল ফেসবুক গুগল লিঙ্কডইন মাইক্রোসফট আকাশবাণী ServiceNow টুইটার উবার
বিন্যাস ডেটাামিনার বাছাই করা

সমস্যা সন্নিবেশ বিরতি লেটকোড সমাধান আমাদের কিছু বিরতি এবং একটি পৃথক ব্যবধানের তালিকা সরবরাহ করে। তারপরে আমাদের অন্তরগুলির তালিকার মধ্যে এই নতুন ব্যবধানটি সন্নিবেশ করানোর জন্য বলা হয়। সুতরাং, নতুন অন্তর অন্তরগুলি ছেদ করছে যা ইতিমধ্যে তালিকায় রয়েছে, বা এটি নাও পারে। যদি কোনও ছেদ থাকে তবে আমরা অন্তরগুলিকে একীভূত করি। অন্যথায়, আমরা কেবলমাত্র এমন একটি স্থানে সন্নিবেশ করি যেখানে এটি অন্তরগুলির তালিকার আরোহণ ক্রম অনুসরণ করে।

অন্তর্বর্তী লেটকোড সমাধান sertোকান

উদাহরণ

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

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), কারণ আমরা কেবলমাত্র তালিকাটি পেরিয়েছি এবং আউটপুট ভেক্টরে অন্তরগুলি সন্নিবেশ করিয়েছি। সুতরাং, এই সমস্ত অপারেশন লিনিয়ার সময় নেয়।

স্পেস জটিলতা ity

চালু), কারণ আমরা ভেক্টরগুলির একটি নতুন ভেক্টর তৈরি করেছি যা এন বা এন + 1 উপাদান সঞ্চয় করে। স্থান জটিলতাও লিনিয়ার।