ໃສ່ Interval Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ ເຟສບຸກ ກູໂກ LinkedIn Microsoft Oracle ServiceNow Twitter Uber
Array Dataminr ການຈັດລຽງ

ບັນຫາການແກ້ໄຂບັນຫາກ່ຽວກັບການໃສ່ໄລຍະເວລາຂອງອິນເຕີເນັດ (The Interval Leetcode Solution) ໃຫ້ພວກເຮົາມີບັນຊີລາຍຊື່ຂອງໄລຍະຫ່າງແລະໄລຍະຫ່າງຕ່າງກັນ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາຖືກບອກໃຫ້ໃສ່ໄລຍະ ໃໝ່ ນີ້ໃນບັນຊີລາຍຊື່ຂອງໄລຍະຫ່າງ. ດັ່ງນັ້ນ, ໄລຍະຫ່າງ ໃໝ່ ອາດຈະແມ່ນການຕັດກັນກັບໄລຍະທີ່ມີຢູ່ແລ້ວໃນບັນຊີ, ຫຼືມັນອາດຈະບໍ່ແມ່ນ. ໃນກໍລະນີມີການຕັດກັນທີ່ພວກເຮົາລວມກັນເປັນໄລຍະ. ຖ້າບໍ່ດັ່ງນັ້ນ, ພວກເຮົາພຽງແຕ່ໃສ່ໃນ ຕຳ ແໜ່ງ ທີ່ມັນ ດຳ ເນີນຕາມ ລຳ ດັບຕັ້ງຂອງລາຍຊື່ໄລຍະຫ່າງ.

ໃສ່ Interval Leetcode Solution

ຍົກຕົວຢ່າງ

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

ຄຳ ອະທິບາຍ: ໄລຍະຫ່າງ ໃໝ່ ກຳ ລັງໂຕ້ຕອບກັບໄລຍະຫ່າງ ທຳ ອິດໃນບັນຊີ. ສະນັ້ນໄລຍະຫ່າງ ໃໝ່ ກໍ່ຖືກລວມເຂົ້າກັບໄລຍະ ທຳ ອິດ. ແລະນັ້ນແມ່ນວິທີທີ່ພວກເຮົາຍັງເຫຼືອຢູ່ກັບຜົນຜະລິດທີ່ໄດ້ຮັບ.

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

ຄໍາອະທິບາຍ: ໃນເບື້ອງຕົ້ນ, ເນື່ອງຈາກວ່າບໍ່ມີໄລຍະຫ່າງໃນບັນຊີ. ພວກເຮົາພຽງແຕ່ໃສ່ໄລຍະ ໃໝ່.

ວິທີການ ສຳ ລັບການແຊກໃສ່ລະຍະຂອງໄລຍະຫ່າງແບບ Leetcode

ບັນຫາການແກ້ໄຂບັນຫາກ່ຽວກັບການໃສ່ໄລຍະເວລາຂອງການໃສ່ອິນເຕີເນັດ (Le Intercode Leetcode Solution) ໃຫ້ພວກເຮົາມີໄລຍະຫ່າງແລະໄລຍະຫ່າງພິເສດທີ່ ຈຳ ເປັນຕ້ອງໄດ້ເອົາເຂົ້າ. ດັ່ງນັ້ນ, ພວກເຮົາສາມາດແກ້ໄຂບັນຫາໄດ້ຖ້າພວກເຮົາສາມາດ ຈຳ ລອງຄວາມເປັນໄປໄດ້ທີ່ອາດຈະເກີດຂື້ນ. ມີສອງຄວາມເປັນໄປໄດ້, ບໍ່ວ່າໄລຍະຫ່າງ ໃໝ່ ຈະຕັດກັນກັບບາງໄລຍະທີ່ມີຢູ່ໃນລາຍຊື່ຫລືມັນບໍ່ມີ. ດັ່ງນັ້ນ, ຖ້າມັນເກີດຂື້ນ, ພວກເຮົາພຽງແຕ່ລວມເອົາພວກມັນໃສ່ບ່ອນອື່ນທີ່ພວກເຮົາວາງໄລຍະຫ່າງຢູ່ໃນ ຕຳ ແໜ່ງ ສະເພາະ. ໂດຍ ຕຳ ແໜ່ງ ທີ່ເຈາະຈົງ, ພວກເຮົາ ໝາຍ ຄວາມວ່າ ຄຳ ສັ່ງທີ່ຂຶ້ນໄປໃນບັນຊີຖືກຮັກສາໄວ້ແມ່ນແຕ່ຫລັງຈາກການແຊກ.

ດັ່ງນັ້ນ, ເພື່ອຈັດການກັບສິ່ງນີ້ພວກເຮົາສ້າງ vector ໃໝ່ (array) ຂອງ vector. ພວກເຮົາເລີ່ມຕົ້ນໃສ່ຊ່ອງຫວ່າງເຂົ້າໄປໃນ vector ຜົນຜະລິດທີ່ສ້າງຂື້ນ ໃໝ່ ນີ້. ພວກເຮົາກວດເບິ່ງວ່າໄລຍະເວລາໃນປະຈຸບັນຊ້ອນກັນກັບໄລຍະຫ່າງທີ່ຈະຕ້ອງໃສ່. ຖ້າພວກເຂົາເຮັດ, ຫຼັງຈາກນັ້ນພວກເຮົາແຍກອອກຈາກວົງຈອນ. ຫຼັງຈາກ loop, ພວກເຮົາກວດເບິ່ງວ່າອົງປະກອບທີ່ຊ້ອນກັນຢູ່ໃນລະຫວ່າງໄລຍະຫ່າງທີ່ມີຢູ່ໃນບັນຊີ. ຖ້າພວກມັນຊໍ້າກັນ, ພວກເຮົາລວມໄລຍະຫ່າງໃນປະຈຸບັນກັບໄລຍະຫ່າງ ໃໝ່ ແລະໃສ່ໄລຍະຫ່າງທີ່ເຫຼືອ. ແຕ່ຖ້າພວກເຂົາບໍ່ເຮັດ, ພວກເຮົາກໍ່ເອົາອົງປະກອບຕ່າງໆເຂົ້າໄປໃນ vector ຜົນຜະລິດຈົນກ່ວາ ຕຳ ແໜ່ງ ເລີ່ມຕົ້ນຂອງໄລຍະຫ່າງຈະ ໜ້ອຍ ກວ່າ ຕຳ ແໜ່ງ ເລີ່ມຕົ້ນຂອງໄລຍະຫ່າງທີ່ຈະຕ້ອງໃສ່. ຫຼັງຈາກນັ້ນພວກເຮົາພຽງແຕ່ໃສ່ໄລຍະ ໃໝ່ ແລະຫຼັງຈາກນັ້ນສ່ວນທີ່ເຫຼືອແມ່ນໄລຍະຫ່າງ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບ Insert Interval Leetcode Solution

#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

ລະຫັດ Java ສຳ ລັບໃສ່ອິນເຕີເນັດ Interval Leetcode Solution

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), ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ຂ້າມຜ່ານບັນຊີລາຍຊື່ແລະເອົາໄລຍະເຂົ້າໄປໃນ vector ຜົນຜະລິດ. ດັ່ງນັ້ນ, ການປະຕິບັດງານທັງ ໝົດ ນີ້ໃຊ້ເວລາເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N), ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ສ້າງ vector ໃໝ່ ຂອງ vector ທີ່ເກັບຮັກສາ N ຫຼື N + 1 ອົງປະກອບ. ຄວາມສັບສົນຂອງພື້ນທີ່ຍັງເປັນເສັ້ນ.