وقفہ لیٹکوڈ حل داخل کریں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون ایپل فیس بک گوگل لنکڈ مائیکروسافٹ اوریکل حاضر سروس ٹویٹر Uber
لڑی ڈیٹاامینر ترتیب

مسئلہ داخل کریں وقفہ لیٹکوڈ حل ہمیں کچھ وقفوں کی فہرست اور ایک الگ وقفہ فراہم کرتا ہے۔ پھر ہمیں کہا جاتا ہے کہ وقفوں کی فہرست میں یہ نیا وقفہ داخل کریں۔ لہذا ، نیا وقفہ ان وقفوں کے ساتھ اختلاط کر رہا ہے جو پہلے سے ہی فہرست میں موجود ہیں ، یا ایسا نہیں ہوسکتا ہے۔ اگر کوئی چوراہا ہوتا ہے تو ہم وقفوں کو ضم کرتے ہیں۔ بصورت دیگر ، ہم محض اس پوزیشن پر داخل کرتے ہیں جہاں یہ وقفوں کی فہرست کے چڑھتے ترتیب کی پیروی کرتا ہے۔

وقفہ لیٹکوڈ حل داخل کریں

مثال کے طور پر

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

وضاحت: نیا وقفہ فہرست میں پہلے وقفے کے ساتھ چوراہا۔ لہذا نیا وقفہ پہلے وقفہ کے ساتھ ملا دیا گیا۔ اور اسی طرح ہم دیئے گئے آؤٹ پٹ کے ساتھ رہ گئے ہیں۔

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

وضاحت: ابتدا میں ، چونکہ فہرست میں کوئی وقفے نہیں تھے۔ ہم نے آسانی سے نیا وقفہ داخل کیا۔

داخل وقفہ لیٹ کوڈ حل کے ل Appro اپروچ

مسئلہ داخل کریں وقفہ لیٹکوڈ حل نے ہمیں کچھ وقفے اور ایک اضافی وقفہ فراہم کیا جس کو داخل کرنے کی ضرورت ہے۔ لہذا ، ہم اس مسئلے کو حل کر سکتے ہیں اگر ہم پیدا ہونے والے امکانات کو تقلید کرسکیں۔ وہاں دو امکانات ہیں ، یا تو نیا وقفہ کچھ وقفوں کے ساتھ آپس میں آتا ہے جو فہرست میں پہلے سے موجود ہے یا ایسا نہیں ہوتا ہے۔ لہذا ، اگر ایسا ہوتا ہے تو ، ہم ان کو محض انضمام کردیں ورنہ ہم وقفہ کو کسی خاص پوزیشن پر رکھتے ہیں۔ مخصوص پوزیشن کے ذریعہ ، ہمارا مطلب ہے کہ فہرست میں چڑھنے کا حکم داخل ہونے کے بعد بھی برقرار رکھا جاتا ہے۔

لہذا ، اس کو سنبھالنے کے لئے ہم ایک نیا ویکٹر تیار کرتے ہیں (صف) ویکٹر کی ہم وقفے کو اس نئے بنائے گئے آؤٹ پٹ ویکٹر میں داخل کرنا شروع کرتے ہیں۔ ہم جانچتے ہیں کہ موجودہ وقفہ داخل ہونے کے وقفے کے ساتھ اوورلپ ہوجاتا ہے۔ اگر وہ کرتے ہیں ، تو ہم لوپ کو توڑ دیتے ہیں۔ لوپ کے بعد ، ہم جانچتے ہیں کہ وہ عنصر جو فہرست میں موجود وقفوں میں شامل ہے۔ اگر وہ اوورلپ ہوجاتے ہیں تو ، ہم موجودہ وقفے کو نئے وقفے کے ساتھ ضم کرتے ہیں اور باقی وقفے داخل کرتے ہیں۔ لیکن اگر وہ ایسا نہیں کرتے ہیں تو ، پھر ہم عناصر کو آؤٹ پٹ ویکٹر میں داخل کرتے ہیں جب تک کہ وقفہ کی ابتدائی پوزیشن وقفے کی ابتدائی پوزیشن سے داخل ہونے والی جگہ سے کم نہ ہو۔ پھر ہم آسانی سے نیا وقفہ داخل کریں اور پھر باقی وقفے۔

ضابطے

وقفہ لیٹ کوڈ حل کے ل for 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 + 1 عناصر کو محفوظ کرتا ہے۔ خلائی پیچیدگی بھی لکیری ہے۔