انٽر ليٽ ڪوڊ حل داخل ڪريو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ايپل ڪريو گوگل LinkedIn، Microsoft جي Oracle سروس Twitter سليمان وساڻ
ڪيريو ڊاڪٽريان جي حساب سان

مسئلو داخل ڪريو ليٽ ڪوڊ حل اسان کي ڪجهه وقتي ۽ هڪ الڳ وقف جي فهرست فراهم ڪندو آهي. پوءِ اسان کي ٻڌايو ويندو آهي ته هي نئون وقفو وقتي فهرست جي وچ ۾ داخل ڪريو. تنهن ڪري ، نئين وقتي وقفي سان ٽڪراش ٿي سگهي ٿو جيڪي اڳ ۾ ئي لسٽ ۾ آهن ، يا ٿي سگهي ٿو نه. صورت ۾ اسان کي هڪ ميڙ هوندو آهي اسان وقفن کي ضم ڪريون ٿا. ٻي صورت ۾ ، اسان کي صرف هڪ پوزيشن ۾ داخل ڪريون ٿا جتي اهو وقتي فهرست جي وڌندڙ ترتيب جي پيروي ڪري ٿو.

انٽر ليٽ ڪوڊ حل داخل ڪريو

مثال

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

وضاحت: نئون وقفو فهرست ۾ پهرين وقفي سان ٽڪندو آهي. تنهن ڪري نئون وقفو پهريون وقفو سان ملائي ويندو آهي. ۽ انهي طريقي سان اسان ڇڏي ڏنو ويو آهي

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

وضاحت: شروعات ۾ ، جتان لسٽ ۾ ڪابه وقتي نه هئي. اسان آسانيءَ سان نئون وقفو داخل ڪيو.

انٽرويو ليٽ ڪوڊ حل جو طريقيڪار داخل ڪريو

مسئلو داخل ڪريو ليٽ ڪوڊ حل اسان کي ڪجهه وقفو ۽ اضافي وقفو فراهم ڪيو جنهن کي داخل ڪرڻ جي ضرورت آهي. تنهن ڪري ، اسان مسئلي کي حل ڪري سگھون ٿا جيڪڏهن اسان انهن پيدا ٿيڻ جي امڪانن کي سمايل ڪريون. هتي ٻه امڪان آهن ، يا ته نئون وقتي پهريان موجود فهرستن سان ڳن intيل آهي يا اڳ ۾ ئي موجود نه آهي. تنهن ڪري ، جيڪڏهن اهو ٿئي ٿو ، اسان صرف انهن کي ضم ڪري وٺون ٿا اسان وقفي هڪ خاص پوزيشن تي رکون ٿا. خاص پوزيشن جي ذريعي ، اسان جو مطلب اهو آهي ته لسٽ ۾ جڙڻ وارو حڪم داخل ٿيڻ بعد به برقرار آهي.

تنهن ڪري ، انهي کي سنڀالڻ لاءِ اسان هڪ نئون ویکٹر ٺاهيون ٿا (صفویکٹرن جو. اسان هن نئين پيدا ڪيل آئوٽ ويڪٽر ۾ وقفو داخل ڪرڻ شروع ڪيو. اسان چڪاسون ٿا ته ڇا موجوده وقفي داخل ٿيڻ جي وقفي سان چڙهي وئي آهي. جيڪڏهن اهي ڪندا آهن ، پوء اسان لوپ مان ڀ breakي ويندا آهيون. لوپ کان پوءِ ، اسان چيڪ ڪندا آهيون ته عنصر جيڪا مٿي چڙهيل آهي فهرست ۾ موجود وقفن مان آهي. جيڪڏهن اهي مٿي چڙهندا آهن ، اسان موجوده وقفي کي نئين وقفي سان ملائي ۽ باقي وقفي سان داخل ڪريون. پر جيڪڏهن اهي نه ٿا ڪن ، ته اسان عناصر کي آئوٽ ويٽر ۾ داخل ڪريو ٿا ، جيستائين انٽالل جي شروعاتي پوزيشن داخل ٿيڻ واري وقتي جي شروعاتي پوزيشن کان گهٽ آهي. پوءِ اسان بس نئون وقفو ۽ پوءِ باقي وقفو داخل ڪريون ٿا.

ڪوڊ

انٽر + ليٽ ڪوڊ حل داخل ڪرڻ لاءِ سي ++ ڪوڊ

#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 عنصرن کي ذخيرو ڪري ٿو. خلائي پيچيدگي پڻ سڌي آھي.