ಮಧ್ಯಂತರ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಸೇರಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಆಪಲ್ ಫೇಸ್ಬುಕ್ ಗೂಗಲ್ ಸಂದೇಶ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒರಾಕಲ್ ಸೇವೆ ಈಗ ಟ್ವಿಟರ್ ಉಬರ್
ಅರೇ ಡಾಟಾಮಿನ್ರ್ ವಿಂಗಡಿಸಿ

ಮಧ್ಯಂತರ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಸೇರಿಸುವ ಸಮಸ್ಯೆ ನಮಗೆ ಕೆಲವು ಮಧ್ಯಂತರಗಳ ಪಟ್ಟಿಯನ್ನು ಮತ್ತು ಒಂದು ಪ್ರತ್ಯೇಕ ಮಧ್ಯಂತರವನ್ನು ಒದಗಿಸುತ್ತದೆ. ನಂತರ ಮಧ್ಯಂತರಗಳ ಪಟ್ಟಿಯಲ್ಲಿ ಈ ಹೊಸ ಮಧ್ಯಂತರವನ್ನು ಸೇರಿಸಲು ನಮಗೆ ತಿಳಿಸಲಾಗಿದೆ. ಆದ್ದರಿಂದ, ಹೊಸ ಮಧ್ಯಂತರವು ಈಗಾಗಲೇ ಪಟ್ಟಿಯಲ್ಲಿರುವ ಮಧ್ಯಂತರಗಳೊಂದಿಗೆ ect ೇದಿಸುತ್ತಿರಬಹುದು, ಅಥವಾ ಇರಬಹುದು. ಒಂದು ವೇಳೆ ನಾವು ers ೇದಕವನ್ನು ಹೊಂದಿದ್ದರೆ ನಾವು ಮಧ್ಯಂತರಗಳನ್ನು ವಿಲೀನಗೊಳಿಸುತ್ತೇವೆ. ಇಲ್ಲದಿದ್ದರೆ, ಮಧ್ಯಂತರಗಳ ಪಟ್ಟಿಯ ಆರೋಹಣ ಕ್ರಮವನ್ನು ಅನುಸರಿಸುವ ಸ್ಥಾನದಲ್ಲಿ ನಾವು ಸುಮ್ಮನೆ ಸೇರಿಸುತ್ತೇವೆ.

ಮಧ್ಯಂತರ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಸೇರಿಸಿ

ಉದಾಹರಣೆ

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

ವಿವರಣೆ: ಹೊಸ ಮಧ್ಯಂತರವು ಪಟ್ಟಿಯ ಮೊದಲ ಮಧ್ಯಂತರದೊಂದಿಗೆ ects ೇದಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ ಹೊಸ ಮಧ್ಯಂತರವನ್ನು ಮೊದಲ ಮಧ್ಯಂತರದೊಂದಿಗೆ ವಿಲೀನಗೊಳಿಸಲಾಗಿದೆ. ಮತ್ತು ಕೊಟ್ಟಿರುವ with ಟ್‌ಪುಟ್‌ನೊಂದಿಗೆ ನಾವು ಹೇಗೆ ಉಳಿದಿದ್ದೇವೆ.

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

ವಿವರಣೆ: ಆರಂಭದಲ್ಲಿ, ಪಟ್ಟಿಯಲ್ಲಿ ಯಾವುದೇ ಮಧ್ಯಂತರಗಳಿಲ್ಲದ ಕಾರಣ. ನಾವು ಹೊಸ ಮಧ್ಯಂತರವನ್ನು ಸರಳವಾಗಿ ಸೇರಿಸಿದ್ದೇವೆ.

ಮಧ್ಯಂತರ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಸೇರಿಸಲು ಅನುಸಂಧಾನ

ಇನ್ಸರ್ಟ್ ಇಂಟರ್ವಲ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ನಮಗೆ ಕೆಲವು ಮಧ್ಯಂತರಗಳನ್ನು ಮತ್ತು ಸೇರಿಸಬೇಕಾದ ಹೆಚ್ಚುವರಿ ಮಧ್ಯಂತರವನ್ನು ಒದಗಿಸಿದೆ. ಆದ್ದರಿಂದ, ನಾವು ಉದ್ಭವಿಸಬಹುದಾದ ಸಾಧ್ಯತೆಗಳನ್ನು ಅನುಕರಿಸಲು ಸಾಧ್ಯವಾದರೆ ನಾವು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಬಹುದು. ಎರಡು ಸಾಧ್ಯತೆಗಳಿವೆ, ಹೊಸ ಮಧ್ಯಂತರವು ಪಟ್ಟಿಯಲ್ಲಿ ಈಗಾಗಲೇ ಇರುವ ಕೆಲವು ಮಧ್ಯಂತರಗಳೊಂದಿಗೆ ects ೇದಿಸುತ್ತದೆ ಅಥವಾ ಅದು ಆಗುವುದಿಲ್ಲ. ಆದ್ದರಿಂದ, ಅದು ಮಾಡಿದರೆ, ನಾವು ಅವುಗಳನ್ನು ವಿಲೀನಗೊಳಿಸುತ್ತೇವೆ ಇಲ್ಲದಿದ್ದರೆ ನಾವು ಮಧ್ಯಂತರವನ್ನು ನಿರ್ದಿಷ್ಟ ಸ್ಥಾನದಲ್ಲಿ ಇಡುತ್ತೇವೆ. ನಿರ್ದಿಷ್ಟ ಸ್ಥಾನದ ಪ್ರಕಾರ, ಸೇರಿಸಿದ ನಂತರವೂ ಪಟ್ಟಿಯಲ್ಲಿನ ಆರೋಹಣ ಕ್ರಮವನ್ನು ನಿರ್ವಹಿಸಲಾಗುತ್ತದೆ ಎಂದು ನಾವು ಅರ್ಥೈಸುತ್ತೇವೆ.

ಆದ್ದರಿಂದ, ಇದನ್ನು ನಿರ್ವಹಿಸಲು ನಾವು ಹೊಸ ವೆಕ್ಟರ್ ಅನ್ನು ರಚಿಸುತ್ತೇವೆ (ಸರಣಿ) ವಾಹಕಗಳ. ನಾವು ಹೊಸದಾಗಿ ರಚಿಸಿದ output ಟ್‌ಪುಟ್ ವೆಕ್ಟರ್‌ಗೆ ಮಧ್ಯಂತರಗಳನ್ನು ಸೇರಿಸಲು ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ. ಸೇರಿಸಬೇಕಾದ ಮಧ್ಯಂತರದೊಂದಿಗೆ ಪ್ರಸ್ತುತ ಮಧ್ಯಂತರವು ಅತಿಕ್ರಮಿಸುತ್ತದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅವರು ಹಾಗೆ ಮಾಡಿದರೆ, ನಾವು ಲೂಪ್ನಿಂದ ಹೊರಬರುತ್ತೇವೆ. ಲೂಪ್ ನಂತರ, ಅತಿಕ್ರಮಿಸುವ ಅಂಶವು ಪಟ್ಟಿಯಲ್ಲಿರುವ ಮಧ್ಯಂತರಗಳಲ್ಲಿ ಇದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅವು ಅತಿಕ್ರಮಿಸಿದರೆ, ನಾವು ಪ್ರಸ್ತುತ ಮಧ್ಯಂತರವನ್ನು ಹೊಸ ಮಧ್ಯಂತರದೊಂದಿಗೆ ವಿಲೀನಗೊಳಿಸುತ್ತೇವೆ ಮತ್ತು ಉಳಿದ ಮಧ್ಯಂತರಗಳನ್ನು ಸೇರಿಸುತ್ತೇವೆ. ಆದರೆ ಅವರು ಹಾಗೆ ಮಾಡದಿದ್ದರೆ, ಮಧ್ಯಂತರದ ಪ್ರಾರಂಭದ ಸ್ಥಾನವು ಸೇರಿಸಬೇಕಾದ ಮಧ್ಯಂತರದ ಆರಂಭಿಕ ಸ್ಥಾನಕ್ಕಿಂತ ಕಡಿಮೆಯಾಗುವವರೆಗೆ ನಾವು elements ಟ್‌ಪುಟ್ ವೆಕ್ಟರ್‌ಗೆ ಅಂಶಗಳನ್ನು ಸೇರಿಸುತ್ತೇವೆ. ನಂತರ ನಾವು ಹೊಸ ಮಧ್ಯಂತರವನ್ನು ಸೇರಿಸುತ್ತೇವೆ ಮತ್ತು ನಂತರ ಉಳಿದ ಮಧ್ಯಂತರಗಳನ್ನು ಸೇರಿಸುತ್ತೇವೆ.

ಕೋಡ್

ಮಧ್ಯಂತರ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಸೇರಿಸಲು ಸಿ ++ ಕೋಡ್

#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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಪಟ್ಟಿಯ ಮೇಲೆ ಸರಳವಾಗಿ ಸಂಚರಿಸಿದ್ದೇವೆ ಮತ್ತು ಮಧ್ಯಂತರಗಳನ್ನು output ಟ್‌ಪುಟ್ ವೆಕ್ಟರ್‌ಗೆ ಸೇರಿಸಿದ್ದೇವೆ. ಆದ್ದರಿಂದ, ಈ ಎಲ್ಲಾ ಕಾರ್ಯಾಚರಣೆಗಳು ರೇಖೀಯ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು N ಅಥವಾ N + 1 ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸುವ ಹೊಸ ವೆಕ್ಟರ್‌ಗಳನ್ನು ರಚಿಸಿದ್ದೇವೆ. ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯೂ ರೇಖೀಯವಾಗಿದೆ.