แทรก Interval Leetcode Solution


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน แอปเปิล Facebook Google LinkedIn ไมโครซอฟท์ คำพยากรณ์ ServiceNow Twitter Uber
แถว Dataminrmin ประเภท

ปัญหา Insert Interval Leetcode Solution ช่วยให้เรามีรายการช่วงเวลาบางช่วงและช่วงเวลาที่แยกจากกัน จากนั้นเราจะบอกให้แทรกช่วงเวลาใหม่นี้ในรายการช่วงเวลา ดังนั้นช่วงเวลาใหม่อาจตัดกับช่วงเวลาที่มีอยู่แล้วในรายการหรืออาจไม่ ในกรณีที่มีจุดตัดเราจะรวมช่วงเวลา มิฉะนั้นเราเพียงแค่แทรกในตำแหน่งที่เป็นไปตามลำดับจากน้อยไปหามากของรายการช่วงเวลา

แทรก Interval Leetcode Solution

ตัวอย่าง

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

คำอธิบาย: ช่วงเวลาใหม่ตัดกับช่วงแรกในรายการ ดังนั้นช่วงเวลาใหม่จะถูกรวมเข้ากับช่วงเวลาแรก และนั่นคือวิธีที่เราเหลือเอาท์พุทที่กำหนด

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

คำอธิบาย: เริ่มแรกเนื่องจากไม่มีช่วงเวลาในรายการ เราเพียงแค่แทรกช่วงเวลาใหม่

แนวทางในการแทรก Interval Leetcode Solution

ปัญหา Insert Interval Leetcode Solution ทำให้เรามีช่วงเวลาและช่วงเวลาพิเศษที่ต้องแทรก ดังนั้นเราสามารถแก้ปัญหาได้หากเราสามารถจำลองความเป็นไปได้ที่อาจเกิดขึ้น มีความเป็นไปได้สองอย่างคือช่วงเวลาใหม่ตัดกับช่วงเวลาบางช่วงที่มีอยู่แล้วในรายการหรือไม่มี ดังนั้นถ้าเป็นเช่นนั้นเราก็รวมเข้าด้วยกันเราวางช่วงเวลาไว้ที่ตำแหน่งเฉพาะ ตามตำแหน่งเฉพาะเราหมายความว่าลำดับจากน้อยไปหามากในรายการจะยังคงอยู่แม้หลังจากการแทรกแล้วก็ตาม

ดังนั้นเพื่อจัดการสิ่งนี้เราจึงสร้างเวกเตอร์ใหม่ (แถว) ของเวกเตอร์ เราเริ่มแทรกช่วงเวลาลงในเวกเตอร์เอาต์พุตที่สร้างขึ้นใหม่นี้ เราตรวจสอบว่าช่วงเวลาปัจจุบันทับซ้อนกับช่วงเวลาที่จะแทรกหรือไม่ ถ้าเป็นเช่นนั้นเราก็จะหลุดออกจากวง หลังจากวนซ้ำเราจะตรวจสอบว่าองค์ประกอบที่ทับซ้อนกันอยู่ระหว่างช่วงเวลาที่มีอยู่ในรายการหรือไม่ หากซ้อนทับกันเราจะรวมช่วงเวลาปัจจุบันกับช่วงเวลาใหม่และแทรกช่วงเวลาที่เหลือ แต่ถ้าไม่เป็นเช่นนั้นเราจะแทรกองค์ประกอบลงในเวกเตอร์เอาต์พุตจนกว่าตำแหน่งเริ่มต้นของช่วงเวลาจะน้อยกว่าตำแหน่งเริ่มต้นของช่วงเวลาที่จะแทรก จากนั้นเราก็แทรกช่วงเวลาใหม่แล้วจึงเว้นช่วงเวลาที่เหลือ

รหัส

รหัส 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 สำหรับ Insert 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 หรือ N + 1 ความซับซ้อนของพื้นที่ยังเป็นเส้นตรง