ഇടവേള ലീറ്റ്കോഡ് പരിഹാരം ചേർക്കുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ ഫേസ്ബുക്ക് ഗൂഗിൾ ലിങ്ക്ഡ് മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ സർവീസ് ഇപ്പോൾ ട്വിറ്റർ യൂബർ
അറേ ഡാറ്റാമിൻ അടുക്കുക

ഇന്റർവെറ്റ് ലീറ്റ്കോഡ് പരിഹാരം ഉൾപ്പെടുത്തുക എന്ന പ്രശ്നം ഞങ്ങൾക്ക് ചില ഇടവേളകളുടെ ഒരു ലിസ്റ്റും ഒരു പ്രത്യേക ഇടവേളയും നൽകുന്നു. ഈ പുതിയ ഇടവേള ഇടവേളകളുടെ പട്ടികയിൽ ഉൾപ്പെടുത്താൻ ഞങ്ങളോട് പറയുന്നു. അതിനാൽ, പുതിയ ഇടവേള ഇതിനകം പട്ടികയിലുള്ള ഇടവേളകളുമായി വിഭജിക്കുന്നുണ്ടാകാം, അല്ലെങ്കിൽ സംഭവിക്കാനിടയില്ല. ഒരു വിഭജനം ഉണ്ടെങ്കിൽ ഞങ്ങൾ ഇടവേളകൾ ലയിപ്പിക്കുന്നു. അല്ലെങ്കിൽ, ഇടവേളകളുടെ പട്ടികയുടെ ആരോഹണ ക്രമം പിന്തുടരുന്ന ഒരു സ്ഥാനത്ത് ഞങ്ങൾ തിരുകുക.

ഇടവേള ലീറ്റ്കോഡ് പരിഹാരം ചേർക്കുക

ഉദാഹരണം

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

വിശദീകരണം: പുതിയ ഇടവേള ലിസ്റ്റിലെ ആദ്യ ഇടവേളയുമായി വിഭജിക്കുന്നു. അതിനാൽ പുതിയ ഇടവേള ആദ്യ ഇടവേളയുമായി ലയിപ്പിക്കുന്നു. തന്നിരിക്കുന്ന .ട്ട്‌പുട്ടിൽ അവശേഷിക്കുന്നത് അങ്ങനെയാണ്.

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

വിശദീകരണം: തുടക്കത്തിൽ, പട്ടികയിൽ ഇടവേളകളില്ലാത്തതിനാൽ. ഞങ്ങൾ പുതിയ ഇടവേള ചേർത്തു.

ഇടവേള ലീട്ട്‌കോഡ് പരിഹാരം ഉൾപ്പെടുത്തുന്നതിനുള്ള സമീപനം

തിരുകൽ ഇടവേള ലീറ്റ്കോഡ് പരിഹാരം ഞങ്ങൾക്ക് ചില ഇടവേളകളും ഉൾപ്പെടുത്തേണ്ട അധിക ഇടവേളയും നൽകി. അതിനാൽ, ഉണ്ടാകാനിടയുള്ള സാധ്യതകളെ അനുകരിക്കാൻ കഴിയുമെങ്കിൽ ഞങ്ങൾക്ക് പ്രശ്നം പരിഹരിക്കാൻ കഴിയും. രണ്ട് സാധ്യതകളുണ്ട്, ഒന്നുകിൽ പുതിയ ഇടവേള പട്ടികയിൽ ഇതിനകം തന്നെ ചില ഇടവേളകളുമായി വിഭജിക്കുന്നു അല്ലെങ്കിൽ ഇല്ല. അതിനാൽ, അങ്ങനെ സംഭവിക്കുകയാണെങ്കിൽ, ഞങ്ങൾ അവയെ ലയിപ്പിക്കുക, അല്ലെങ്കിൽ ഇടവേള ഒരു നിർദ്ദിഷ്ട സ്ഥാനത്ത് സ്ഥാപിക്കുക. നിർദ്ദിഷ്ട സ്ഥാനം അനുസരിച്ച്, പട്ടികയിലെ ആരോഹണ ക്രമം തിരുകിയതിനുശേഷവും നിലനിർത്തുന്നു എന്നാണ് ഞങ്ങൾ അർത്ഥമാക്കുന്നത്.

അതിനാൽ, ഇത് കൈകാര്യം ചെയ്യാൻ ഞങ്ങൾ ഒരു പുതിയ വെക്റ്റർ സൃഷ്ടിക്കുന്നു (ശ്രേണി) വെക്റ്ററുകളുടെ. പുതുതായി സൃഷ്ടിച്ച output ട്ട്‌പുട്ട് വെക്ടറിലേക്ക് ഞങ്ങൾ ഇടവേളകൾ ചേർക്കാൻ ആരംഭിക്കുന്നു. ഉൾപ്പെടുത്തേണ്ട ഇടവേളയുമായി നിലവിലെ ഇടവേള ഓവർലാപ്പ് ചെയ്യുന്നുണ്ടോ എന്ന് ഞങ്ങൾ പരിശോധിക്കുന്നു. അവർ അങ്ങനെ ചെയ്യുകയാണെങ്കിൽ, ഞങ്ങൾ ലൂപ്പിൽ നിന്ന് പുറത്തുപോകുന്നു. ലൂപ്പിന് ശേഷം, ഓവർലാപ്പ് ചെയ്യുന്ന ഘടകം ലിസ്റ്റിലെ ഇടവേളകളിൽ ഉണ്ടോ എന്ന് ഞങ്ങൾ പരിശോധിക്കുന്നു. അവ ഓവർലാപ്പ് ചെയ്യുകയാണെങ്കിൽ, നിലവിലെ ഇടവേള ഞങ്ങൾ പുതിയ ഇടവേളയുമായി ലയിപ്പിക്കുകയും ബാക്കി ഇടവേളകൾ ചേർക്കുകയും ചെയ്യുന്നു. അവ അങ്ങനെ ചെയ്യുന്നില്ലെങ്കിൽ, ഇടവേളയുടെ ആരംഭ സ്ഥാനം ഉൾപ്പെടുത്തേണ്ട ഇടവേളയുടെ ആരംഭ സ്ഥാനത്തേക്കാൾ കുറവാകുന്നതുവരെ ഞങ്ങൾ 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), കാരണം ഞങ്ങൾ പട്ടികയിലൂടെ സഞ്ചരിച്ച് ഇടവേളകൾ ve ട്ട്‌പുട്ട് വെക്ടറിൽ ചേർത്തു. അതിനാൽ, ഈ പ്രവർത്തനങ്ങളെല്ലാം രേഖീയ സമയമെടുക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), കാരണം ഞങ്ങൾ N അല്ലെങ്കിൽ N + 1 ഘടകങ്ങൾ സംഭരിക്കുന്ന വെക്റ്ററുകളുടെ ഒരു പുതിയ വെക്റ്റർ സൃഷ്ടിച്ചു. സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.