ਅੰਤਰਾਲ ਲੀਟਕੋਡ ਹੱਲ ਸ਼ਾਮਲ ਕਰੋ  


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਸੇਬ ਫੇਸਬੁੱਕ ਗੂਗਲ ਸਬੰਧਤ Microsoft ਦੇ ਓਰੇਕਲ ਸਰਵਿਸਨੂ ਟਵਿੱਟਰ ਉਬੇਰ
ਐਲਗੋਰਿਥਮ ਅਰੇ ਕੋਡਿੰਗ ਡਾਟਾਮਿਨਰ ਇੰਟਰਵਿਊ ਇੰਟਰਵਿ interview ਦੀ ਤਿਆਰੀ ਲੀਟਕੋਡ LeetCodeSolutions ਲੜੀਬੱਧ

ਸਮੱਸਿਆ ਦਾਖਲ ਅੰਤਰਾਲ ਲੀਟਕੋਡ ਹੱਲ ਸਾਨੂੰ ਕੁਝ ਅੰਤਰਾਲਾਂ ਅਤੇ ਇੱਕ ਵੱਖਰੇ ਅੰਤਰਾਲ ਦੀ ਸੂਚੀ ਪ੍ਰਦਾਨ ਕਰਦਾ ਹੈ. ਫਿਰ ਸਾਨੂੰ ਦੱਸਿਆ ਜਾਂਦਾ ਹੈ ਕਿ ਇਸ ਨਵੇਂ ਅੰਤਰਾਲ ਨੂੰ ਅੰਤਰਾਲਾਂ ਦੀ ਸੂਚੀ ਵਿਚ ਸ਼ਾਮਲ ਕਰੋ. ਇਸ ਲਈ, ਸ਼ਾਇਦ ਨਵਾਂ ਅੰਤਰਾਲ ਅੰਤਰਾਲਾਂ ਨਾਲ ਜੋੜਿਆ ਜਾ ਰਿਹਾ ਹੈ ਜੋ ਪਹਿਲਾਂ ਹੀ ਸੂਚੀ ਵਿੱਚ ਹਨ, ਜਾਂ ਹੋ ਸਕਦਾ ਹੈ ਕਿ ਇਹ ਨਾ ਹੋਵੇ. ਜੇ ਕੋਈ ਲਾਂਘਾ ਹੋਵੇ ਤਾਂ ਅਸੀਂ ਅੰਤਰਾਲਾਂ ਨੂੰ ਮਿਲਾ ਦਿੰਦੇ ਹਾਂ. ਨਹੀਂ ਤਾਂ, ਅਸੀਂ ਸਧਾਰਣ ਤੌਰ ਤੇ ਅਜਿਹੀ ਸਥਿਤੀ ਵਿੱਚ ਪਾਉਂਦੇ ਹਾਂ ਜਿੱਥੇ ਇਹ ਅੰਤਰਾਲਾਂ ਦੀ ਸੂਚੀ ਦੇ ਚੜ੍ਹਦੇ ਕ੍ਰਮ ਦੀ ਪਾਲਣਾ ਕਰਦਾ ਹੈ.

ਅੰਤਰਾਲ ਲੀਟਕੋਡ ਹੱਲ ਸ਼ਾਮਲ ਕਰੋਪਿੰਨ

ਉਦਾਹਰਨ  

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

ਵਿਆਖਿਆ: ਨਵਾਂ ਅੰਤਰਾਲ ਸੂਚੀ ਦੇ ਪਹਿਲੇ ਅੰਤਰਾਲ ਦੇ ਨਾਲ ਕੱਟਦਾ ਹੈ. ਇਸ ਲਈ ਨਵਾਂ ਅੰਤਰਾਲ ਪਹਿਲੇ ਅੰਤਰਾਲ ਨਾਲ ਮਿਲਾਇਆ ਜਾਂਦਾ ਹੈ. ਅਤੇ ਇਵੇਂ ਹੀ ਅਸੀਂ ਦਿੱਤੇ ਆਉਟਪੁੱਟ ਨਾਲ ਬਚੇ ਹੋਏ ਹਾਂ.

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

ਵਿਆਖਿਆ: ਸ਼ੁਰੂਆਤ ਵਿੱਚ, ਕਿਉਂਕਿ ਸੂਚੀ ਵਿੱਚ ਕੋਈ ਅੰਤਰਾਲ ਨਹੀਂ ਸਨ. ਅਸੀਂ ਅਸਾਨੀ ਨਾਲ ਨਵਾਂ ਅੰਤਰਾਲ ਪਾਇਆ.

ਇਨਸਰਟ ਇੰਟਰਵਲ ਲੈਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਲਈ ਪਹੁੰਚ  

ਸਮੱਸਿਆ ਦਾਖਲ ਅੰਤਰਾਲ ਲੀਟਕੋਡ ਹੱਲ ਨੇ ਸਾਨੂੰ ਕੁਝ ਅੰਤਰਾਲ ਅਤੇ ਇੱਕ ਵਾਧੂ ਅੰਤਰਾਲ ਪ੍ਰਦਾਨ ਕੀਤਾ ਜਿਸ ਨੂੰ ਪਾਉਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇਸ ਲਈ, ਅਸੀਂ ਸਮੱਸਿਆ ਦਾ ਹੱਲ ਕੱ if ਸਕਦੇ ਹਾਂ ਜੇ ਅਸੀਂ ਪੈਦਾ ਹੋਈਆਂ ਸੰਭਾਵਨਾਵਾਂ ਦਾ ਨਕਲ ਕਰ ਸਕੀਏ. ਇੱਥੇ ਦੋ ਸੰਭਾਵਨਾਵਾਂ ਹਨ, ਜਾਂ ਤਾਂ ਨਵਾਂ ਅੰਤਰਾਲ ਕੁਝ ਅੰਤਰਾਲਾਂ ਨਾਲ ਲਟਕਦਾ ਹੈ ਜੋ ਪਹਿਲਾਂ ਹੀ ਸੂਚੀ ਵਿੱਚ ਮੌਜੂਦ ਹਨ ਜਾਂ ਇਹ ਨਹੀਂ ਹੁੰਦਾ. ਇਸ ਲਈ, ਜੇ ਇਹ ਹੁੰਦਾ ਹੈ, ਅਸੀਂ ਉਨ੍ਹਾਂ ਨੂੰ ਸਿਰਫ਼ ਅਭੇਦ ਕਰ ਦਿੰਦੇ ਹਾਂ ਨਹੀਂ ਤਾਂ ਅਸੀਂ ਅੰਤਰਾਲ ਨੂੰ ਇਕ ਖਾਸ ਸਥਿਤੀ 'ਤੇ ਰੱਖਦੇ ਹਾਂ. ਖਾਸ ਸਥਿਤੀ ਦੁਆਰਾ, ਸਾਡਾ ਮਤਲਬ ਹੈ ਕਿ ਸੂਚੀ ਵਿੱਚ ਚੜਾਈ ਦਾ ਕ੍ਰਮ ਸੰਮਿਲਨ ਦੇ ਬਾਅਦ ਵੀ ਬਣਾਈ ਰੱਖਿਆ ਜਾਂਦਾ ਹੈ.

ਇਹ ਵੀ ਵੇਖੋ
ਸਾਰੇ ਸੰਤਰੇ ਨੂੰ ਸੜਨ ਲਈ ਘੱਟੋ ਘੱਟ ਸਮਾਂ

ਇਸ ਲਈ, ਇਸ ਨੂੰ ਸੰਭਾਲਣ ਲਈ ਅਸੀਂ ਇੱਕ ਨਵਾਂ ਵੈਕਟਰ ਬਣਾਉਂਦੇ ਹਾਂ (ਐਰੇ) ਵੈਕਟਰ ਦੇ. ਅਸੀਂ ਇਸ ਨਵੇਂ ਬਣੇ ਆਉਟਪੁੱਟ ਵੈਕਟਰ ਵਿਚ ਅੰਤਰਾਲ ਪਾਉਣਾ ਅਰੰਭ ਕਰਦੇ ਹਾਂ. ਅਸੀਂ ਜਾਂਚ ਕਰਦੇ ਹਾਂ ਕਿ ਕੀ ਮੌਜੂਦਾ ਅੰਤਰਾਲ ਪਾਉਣ ਦੇ ਅੰਤਰਾਲ ਨਾਲ ਓਵਰਲੈਪ ਹੁੰਦਾ ਹੈ. ਜੇ ਉਹ ਕਰਦੇ ਹਨ, ਤਾਂ ਅਸੀਂ ਲੂਪ ਤੋਂ ਵੱਖ ਹੋ ਜਾਂਦੇ ਹਾਂ. ਲੂਪ ਤੋਂ ਬਾਅਦ, ਅਸੀਂ ਜਾਂਚ ਕਰਦੇ ਹਾਂ ਕਿ ਉਹ ਤੱਤ ਜੋ ਓਵਰਲੈਪ ਹੁੰਦਾ ਹੈ ਸੂਚੀ ਵਿਚ ਮੌਜੂਦ ਅੰਤਰਾਲਾਂ ਵਿਚੋਂ ਇਕ ਹੈ. ਜੇ ਉਹ ਓਵਰਲੈਪ ਹੋ ਜਾਂਦੇ ਹਨ, ਅਸੀਂ ਮੌਜੂਦਾ ਅੰਤਰਾਲ ਨੂੰ ਨਵੇਂ ਅੰਤਰਾਲ ਨਾਲ ਮਿਲਾ ਦਿੰਦੇ ਹਾਂ ਅਤੇ ਬਾਕੀ ਅੰਤਰਾਲ ਸੰਮਿਲਿਤ ਕਰਦੇ ਹਾਂ. ਪਰ ਜੇ ਉਹ ਨਹੀਂ ਕਰਦੇ, ਤਾਂ ਅਸੀਂ ਤੱਤ ਆਉਟਪੁੱਟ ਵੈਕਟਰ ਵਿਚ ਸੰਮਿਲਿਤ ਕਰਦੇ ਹਾਂ ਜਦੋਂ ਤਕ ਅੰਤਰਾਲ ਦੀ ਸ਼ੁਰੂਆਤੀ ਸਥਿਤੀ ਸੰਮਿਲਿਤ ਹੋਣ ਵਾਲੇ ਅੰਤਰਾਲ ਦੀ ਸ਼ੁਰੂਆਤੀ ਸਥਿਤੀ ਤੋਂ ਘੱਟ ਨਹੀਂ ਹੁੰਦੀ. ਫਿਰ ਅਸੀਂ ਅਸਾਨੀ ਨਾਲ ਨਵਾਂ ਅੰਤਰਾਲ ਪਾਉਂਦੇ ਹਾਂ ਅਤੇ ਫਿਰ ਬਾਕੀ ਅੰਤਰਾਲ.

ਕੋਡ  

ਇਨਸਰਟ ਇੰਟਰਵਲ ਲੈਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਲਈ ਸੀ ++ ਕੋਡ

#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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ  

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਅਸਾਨੀ ਨਾਲ ਸੂਚੀ ਵਿਚੋਂ ਲੰਘ ਚੁੱਕੇ ਹਾਂ ਅਤੇ ਅੰਤਰਾਲਾਂ ਨੂੰ ਆਉਟਪੁਟ ਵੈਕਟਰ ਵਿਚ ਸ਼ਾਮਲ ਕੀਤਾ ਹੈ. ਇਸ ਲਈ, ਇਹ ਸਾਰੇ ਓਪਰੇਸ਼ਨ ਲੰਬੇ ਸਮੇਂ ਲੈਂਦੇ ਹਨ.

ਇਹ ਵੀ ਵੇਖੋ
ਬੀ ਐਸ ਟੀ ਨੋਡਜ਼ ਲੀਟਕੋਡ ਸਲਿolutionਸ਼ਨ ਦੇ ਵਿਚਕਾਰ ਘੱਟੋ ਘੱਟ ਦੂਰੀ

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਵੈਕਟਰਾਂ ਦਾ ਨਵਾਂ ਵੈਕਟਰ ਤਿਆਰ ਕੀਤਾ ਹੈ ਜੋ N ਜਾਂ N + 1 ਤੱਤ ਸਟੋਰ ਕਰਦਾ ਹੈ. ਪੁਲਾੜ ਦੀ ਜਟਿਲਤਾ ਵੀ ਲੀਨੀਅਰ ਹੈ.

1