បញ្ចូលដំណោះស្រាយចន្លោះ Leetcode


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ផ្លែប៉ោម Facebook ក្រុមហ៊ុន google LinkedIn ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle ServiceNow ។ ក្នុង Twitter Uber
អារេ ដេតាមីន តម្រៀប

បញ្ហាបញ្ចូលចន្លោះពេលឡេឡេលេខកូដដំណោះស្រាយផ្តល់ឱ្យយើងនូវបញ្ជីចន្លោះពេលមួយចំនួននិងចន្លោះពេលដាច់ដោយឡែកមួយ។ បន្ទាប់មកយើងត្រូវបានគេប្រាប់ឱ្យបញ្ចូលចន្លោះពេលថ្មីនេះក្នុងចំណោមបញ្ជីចន្លោះពេល។ ដូច្នេះចន្លោះពេលថ្មីអាចនឹងត្រូវបានប្រសព្វគ្នាជាមួយនឹងចន្លោះពេលដែលមាននៅក្នុងបញ្ជីរួចហើយឬវាប្រហែលជាមិនមាន។ ក្នុងករណីមានចំនុចប្រសព្វយើងបញ្ចូលចន្លោះពេល។ បើមិនដូច្នោះទេយើងគ្រាន់តែបញ្ចូលនៅទីតាំងមួយដែលវាធ្វើតាមលំដាប់ឡើងនៃបញ្ជីចន្លោះពេល។

បញ្ចូលដំណោះស្រាយចន្លោះ Leetcode

ឧទាហរណ៍

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

ការពន្យល់ៈចន្លោះពេលថ្មីប្រសព្វគ្នាជាមួយចន្លោះពេលដំបូងក្នុងបញ្ជី។ ដូច្នេះចន្លោះពេលថ្មីត្រូវបានបញ្ចូលគ្នាជាមួយចន្លោះពេលដំបូង។ ហើយនោះជារបៀបដែលយើងនៅសល់ជាមួយនឹងលទ្ធផលដែលបានផ្តល់ឱ្យ។

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

ការពន្យល់ៈដំបូងឡើយដោយសារមិនមានចន្លោះពេលនៅក្នុងបញ្ជី។ យើងគ្រាន់តែបញ្ចូលចន្លោះពេលថ្មី។

វិធីសាស្រ្តក្នុងការបញ្ចូលដំណោះស្រាយឡេឡេកូដចន្លោះពេល

បញ្ហាបញ្ចូលចន្លោះពេលឡេឡិកកូដដំណោះស្រាយផ្តល់ឱ្យយើងនូវចន្លោះពេលមួយចំនួននិងចន្លោះពេលបន្ថែមដែលត្រូវការបញ្ចូល។ ដូច្នេះយើងអាចដោះស្រាយបញ្ហាបានប្រសិនបើយើងអាចក្លែងធ្វើនូវលទ្ធភាពដែលអាចកើតមាន។ មានលទ្ធភាពពីរគឺចន្លោះពេលថ្មីអាចកាត់ជាមួយចន្លោះពេលមួយចំនួនដែលមានរួចហើយនៅក្នុងបញ្ជីឬវាមិនមាន។ ដូច្នេះប្រសិនបើវាកើតឡើងយើងគ្រាន់តែបញ្ចូលវាទៅកន្លែងផ្សេងទៀតយើងដាក់ចន្លោះពេលនៅទីតាំងជាក់លាក់។ តាមទីតាំងជាក់លាក់យើងមានន័យថាលំដាប់ឡើងនៅក្នុងបញ្ជីត្រូវបានរក្សាទុកសូម្បីតែបន្ទាប់ពីការបញ្ចូល។

ដូច្នេះដើម្បីដោះស្រាយវាយើងបង្កើតវ៉ិចទ័រថ្មី (អារេ) នៃវ៉ិចទ័រ។ យើងចាប់ផ្តើមបញ្ចូលចន្លោះពេលទៅក្នុងវ៉ិចទ័រទិន្នផលដែលបានបង្កើតថ្មីនេះ។ យើងពិនិត្យមើលថាតើចន្លោះពេលបច្ចុប្បន្នត្រួតលើគ្នាជាមួយចន្លោះពេលដែលត្រូវបញ្ចូល។ ប្រសិនបើពួកគេធ្វើដូច្នេះយើងបំបែកចេញពីរង្វិលជុំ។ បន្ទាប់ពីរង្វិលជុំយើងពិនិត្យមើលថាតើធាតុដែលត្រួតលើគ្នាស្ថិតក្នុងចំណោមចន្លោះពេលដែលមាននៅក្នុងបញ្ជី។ ប្រសិនបើពួកគេត្រួតលើគ្នាយើងបញ្ចូលចន្លោះពេលបច្ចុប្បន្នជាមួយចន្លោះថ្មីហើយបញ្ចូលចន្លោះពេលនៅសល់។ ប៉ុន្តែប្រសិនបើពួកគេមិនធ្វើដូច្នេះយើងបញ្ចូលធាតុទៅក្នុងវ៉ិចទ័រលទ្ធផលរហូតដល់ទីតាំងចាប់ផ្តើមចន្លោះពេលតិចជាងទីតាំងចាប់ផ្តើមនៃចន្លោះពេលដែលត្រូវបញ្ចូល។ បន្ទាប់មកយើងបញ្ចូលចន្លោះពេលថ្មីហើយបន្ទាប់មកចន្លោះពេលនៅសល់។

លេខកូដ

លេខកូដ C ++ សំរាប់បញ្ចូលចន្លោះពេលឡេឡិកកូដសូលូសិន

#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), ពីព្រោះយើងបានឆ្លងកាត់បញ្ជីហើយបញ្ចូលចន្លោះពេលទៅក្នុងវ៉ិចទ័រលទ្ធផល។ ដូច្នេះប្រតិបត្ដិការទាំងអស់នេះត្រូវការពេលលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

O (N), ពីព្រោះយើងបានបង្កើតវ៉ិចទ័រវ៉ិចទ័រថ្មីដែលផ្ទុកធាតុ N ឬ N + 1 ។ ភាពស្មុគស្មាញនៃអវកាសក៏ជាលីនេអ៊ែរផងដែរ។