અંતરાલ લીટકોડ સોલ્યુશન શામેલ કરો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન ફેસબુક Google LinkedIn માઈક્રોસોફ્ટ ઓરેકલ સેવા હવે Twitter ઉબેર
અરે ડેટામિનર સૉર્ટ

સમસ્યા દાખલ કરો અંતરાલ લીટકોડ સોલ્યુશન અમને કેટલાક અંતરાલોની સૂચિ અને એક અલગ અંતરાલ પ્રદાન કરે છે. પછી અમને અંતરાલની સૂચિમાં આ નવું અંતરાલ દાખલ કરવાનું કહેવામાં આવે છે. તેથી, નવું અંતરાલ અંતરાલો સાથે છેદે છે જે પહેલાથી સૂચિમાં છે, અથવા તે કદાચ નહીં હોય. જો ત્યાં કોઈ આંતરછેદ હોય તો આપણે અંતરાલો મર્જ કરીશું. નહિંતર, અમે ફક્ત તે સ્થાન પર દાખલ કરીએ છીએ જ્યાં તે અંતરાલોની સૂચિના ચડતા ક્રમને અનુસરે છે.

અંતરાલ લીટકોડ સોલ્યુશન શામેલ કરો

ઉદાહરણ

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

સમજૂતી: નવી અંતરાલ સૂચિમાં પ્રથમ અંતરાલ સાથે છેદે છે. તેથી નવા અંતરાલને પ્રથમ અંતરાલમાં મર્જ કરવામાં આવે છે. આપણને આપેલ આઉટપુટ સાથે આ રીતે છોડી દેવામાં આવે છે.

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

સમજૂતી: શરૂઆતમાં, સૂચિમાં કોઈ અંતરાલ ન હોવાથી. અમે ખાલી નવો અંતરાલ દાખલ કર્યો.

ઇનસેલ ઇન્ટરવલ લીટકોડ સોલ્યુશન માટે અભિગમ

સમસ્યા દાખલ કરો અંતરાલ લીટકોડ સોલ્યુશન અમને કેટલાક અંતરાલ અને એક વધારાનો અંતરાલ પૂરો પાડે છે જે દાખલ કરવાની જરૂર છે. તેથી, જો આપણે theભી થઈ શકે તેવી શક્યતાઓનું અનુકરણ કરી શકીએ, તો અમે સમસ્યાનું નિરાકરણ લાવી શકીશું. ત્યાં બે સંભાવનાઓ છે, નવો અંતરાલ કેટલાક અંતરાલો સાથે છેદે છે જે સૂચિમાં પહેલાથી હાજર છે અથવા તે નથી. તેથી, જો તે થાય છે, તો અમે ફક્ત તેમને મર્જ કરીશું અન્યથા આપણે અંતરાલને ચોક્કસ સ્થાન પર મૂકીએ છીએ. વિશિષ્ટ સ્થિતિ દ્વારા, અમારો મતલબ છે કે સૂચિમાં ચડતા ક્રમ દાખલ કર્યા પછી પણ જાળવવામાં આવે છે.

તેથી, આને હેન્ડલ કરવા માટે આપણે એક નવું વેક્ટર બનાવીએ છીએ (એરે) વેક્ટર્સ ઓફ. અમે આ નવા બનાવેલા આઉટપુટ વેક્ટરમાં અંતરાલો દાખલ કરવાનું પ્રારંભ કરીએ છીએ. અમે તપાસો કે શું વર્તમાન અંતરાલ અંતરાલ સાથે દાખલ થવા માટે ઓવરલેપ થાય છે. જો તેઓ કરે છે, તો પછી આપણે લૂપમાંથી બહાર નીકળીએ છીએ. લૂપ પછી, અમે તપાસો કે જે તત્વ ઓવરલેપ થાય છે તે સૂચિમાં હાજર અંતરાલોમાં છે કે કેમ. જો તે ઓવરલેપ થાય છે, તો અમે વર્તમાન અંતરાલને નવા અંતરાલ સાથે મર્જ કરીએ છીએ અને બાકીના અંતરાલો દાખલ કરીશું. પરંતુ જો તે ન થાય, તો પછી અંતરાલની પ્રારંભિક સ્થિતિ દાખલ કરવા માટે અંતરાલની પ્રારંભિક સ્થિતિ કરતા ઓછી ન થાય ત્યાં સુધી અમે તત્વોને આઉટપુટ વેક્ટરમાં શામેલ કરીએ છીએ. પછી અમે ફક્ત નવું અંતરાલ દાખલ કરીએ અને પછી બાકીના અંતરાલો.

કોડ

શામેલ ઇન્ટરવલ લીટકોડ સોલ્યુશન માટે સી ++ કોડ

#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 તત્વો સ્ટોર કરે છે. જગ્યાની જટિલતા પણ રેખીય છે.