අන්තරාන්තර ලීට්කෝඩ් විසඳුම ඇතුළු කරන්න  


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් Apple ජංගම දුරකථන ෆේස්බුක් ගූගල් LinkedIn මයික්රොසොෆ්ට් ඔරකල් සර්විස්නව් ට්විටර් Uber
ඇල්ගොරිතම අරා කේතීකරණය ඩේටමින් සම්මුඛ පරීක්ෂණ සම්මුඛ සාකච්ඡා ලීට්කෝඩ් LeetCodeSolutions වර්ග

ඇතුල් කිරීමේ කාල පරතරය ලීට්කෝඩ් විසඳුම මඟින් අපට යම් කාල පරතරයන් ලැයිස්තුවක් සහ වෙනම කාල පරතරයක් ලබා දේ. මෙම නව පරතරය අන්තරයන් ලැයිස්තුවට ඇතුළත් කරන ලෙස අපට කියනු ලැබේ. එබැවින්, නව පරතරය දැනටමත් ලැයිස්තුවේ ඇති අන්තරයන් සමඟ ඡේදනය විය හැකිය, නැතහොත් එසේ නොවිය හැකිය. ඡේදනයක් තිබේ නම් අපි අන්තරයන් ඒකාබද්ධ කරමු. එසේ නොමැති නම්, අපි එය වර්‍ග ලැයිස්තුවේ නැගීමේ අනුපිළිවෙල අනුගමනය කරන ස්ථානයකට ඇතුළත් කරමු.

අන්තරාන්තර ලීට්කෝඩ් විසඳුම ඇතුළු කරන්නපින්

උදාහරණයක්  

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

පැහැදිලි කිරීම: නව පරතරය ලැයිස්තුවේ පළමු අන්තරය සමඟ සම්බන්ධ වේ. එබැවින් නව පරතරය පළමු අන්තරය සමඟ ඒකාබද්ධ වේ. දී ඇති ප්‍රතිදානය අපට ඉතිරිව ඇත්තේ එලෙස ය.

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

පැහැදිලි කිරීම: මුලදී, ලැයිස්තුවේ කිසිදු කාල පරතරයක් නොතිබූ බැවින්. අපි සරලවම නව පරතරය ඇතුළත් කළෙමු.

අන්තරාන්තර ලීට්කෝඩ් විසඳුම ඇතුළු කිරීම සඳහා ප්‍රවේශය  

ඇතුල් කිරීමේ කාල පරතරය ලීට්කෝඩ් විසඳුම මඟින් අපට යම් කාල පරතරයක් සහ අමතර කාල පරතරයක් ඇතුළත් කළ යුතුය. එබැවින් අපට ඇතිවිය හැකි හැකියාවන් අනුකරණය කළ හැකි නම් අපට ගැටළුව විසඳා ගත හැකිය. හැකියාවන් දෙකක් තිබේ, එක්කෝ නව අන්තරය ලැයිස්තුවේ දැනටමත් ඇති සමහර අන්තරයන් සමඟ සම්බන්ධ වේ හෝ එසේ නොවේ. එබැවින්, එසේ වුවහොත්, අපි ඒවා වෙනත් ආකාරයකින් ඒකාබද්ධ කර, අපි පරතරය නිශ්චිත ස්ථානයක තබමු. නිශ්චිත පිහිටීම අනුව, අපි අදහස් කරන්නේ ලැයිස්තුවේ ආරෝහණ අනුපිළිවෙල ඇතුළත් කිරීමෙන් පසුව පවා පවත්වා ගෙන යන බවයි.

මෙයද බලන්න
සියලුම දොඩම් කුණුවීමට අවශ්‍ය අවම කාලය

ඉතින්, මෙය හැසිරවීමට අපි නව දෛශිකයක් නිර්මාණය කරමු (අරාව) දෛශික. අපි අලුතින් සාදන ලද නිමැවුම් දෛශිකයට අන්තරයන් ඇතුළත් කිරීමට පටන් ගනිමු. වත්මන් අන්තරය ඇතුළු කළ යුතු පරතරය සමඟ අතිච්ඡාදනය වේදැයි අපි පරීක්ෂා කරමු. ඔවුන් එසේ කරන්නේ නම්, අපි ලූපයෙන් ඉවත් වෙමු. ලූපයෙන් පසුව, ලැයිස්තුවේ ඇති අන්තරයන් අතර අතිච්ඡාදනය වන මූලද්‍රව්‍යය තිබේදැයි අපි පරීක්ෂා කරමු. ඒවා අතිච්ඡාදනය වුවහොත්, අපි වත්මන් පරතරය නව පරතරය සමඟ ඒකාබද්ධ කර ඉතිරි කාල පරතරයන් ඇතුළත් කරමු. නමුත් ඒවා එසේ නොවේ නම්, ඇතුල් කළ යුතු කාල පරතරයේ ආරම්භක ස්ථානයට වඩා අන්තරයේ ආරම්භක පිහිටීම අඩු වන තෙක් අපි ප්‍රතිදාන දෛශිකයට මූලද්‍රව්‍ය ඇතුල් කරමු. එවිට අපි සරලවම නව පරතරය ඇතුළු කර ඉතිරි කාල පරතරයන් ඇතුළත් කරමු.

කේතය  

අන්තරාන්තර ලීට්කෝඩ් විසඳුම ඇතුළත් කිරීම සඳහා සී ++ කේතය

#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

සංකීර්ණ විශ්ලේෂණය  

කාල සංකීර්ණත්වය

මත), මන්ද අපි හුදෙක් ලැයිස්තුව හරහා ගමන් කර ප්‍රතිදාන දෛශිකයට අන්තරයන් ඇතුළත් කර ඇති බැවිනි. ඉතින්, මෙම සියලු මෙහෙයුම් සඳහා රේඛීය කාලය ගතවේ.

මෙයද බලන්න
බීඑස්ටී නෝඩ් ලීට්කෝඩ් විසඳුම අතර අවම දුර

අභ්‍යවකාශ සංකීර්ණතාව

මත), අපි N හෝ N + 1 මූලද්‍රව්‍ය ගබඩා කරන නව දෛශික දෛශිකයක් නිර්මාණය කළ නිසා. අවකාශයේ සංකීර්ණතාව ද රේඛීය වේ.

1