インターバルリートコードソリューションを挿入


難易度 ミディアム
よく聞かれる Amazon (アマゾン) Apple Facebook Google LinkedIn マイクロソフト オラクル ServiceNow Twitter ユーバー
配列 データマイナー ソート

問題のInsertInterval Leetcode Solutionは、いくつかの間隔とXNUMXつの個別の間隔のリストを提供します。 次に、この新しい間隔を間隔のリストに挿入するように指示されます。 したがって、新しい間隔は、すでにリストにある間隔と交差している場合と交差していない場合があります。 交差点がある場合は、間隔をマージします。 それ以外の場合は、間隔のリストの昇順に従う位置に挿入するだけです。

インターバルリートコードソリューションを挿入

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

説明:新しい間隔がリストの最初の間隔と交差しています。 したがって、新しい間隔は最初の間隔とマージされます。 そして、それは私たちが与えられた出力を残す方法です。

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

説明:最初は、リストに間隔がなかったためです。 新しい間隔を挿入しただけです。

挿入間隔リートコードソリューションのアプローチ

問題のInsertInterval Leetcode Solutionは、挿入する必要のあるいくつかの間隔と追加の間隔を提供してくれました。 したがって、発生する可能性をシミュレートできれば、問題を解決できます。 新しい間隔がリストにすでに存在するいくつかの間隔と交差するか、交差しないかのXNUMXつの可能性があります。 したがって、そうである場合は、単にそれらをマージします。それ以外の場合は、間隔を特定の位置に配置します。 特定の位置とは、挿入後もリスト内の昇順が維持されることを意味します。

したがって、これを処理するために、新しいベクトルを作成します(配列)ベクトルの。 この新しく作成された出力ベクトルに間隔を挿入し始めます。 現在の間隔が挿入される間隔と重複していないかどうかを確認します。 もしそうなら、私たちはループから抜け出します。 ループの後、重複する要素がリストに存在する間隔の中にあるかどうかを確認します。 それらが重複している場合は、現在の間隔を新しい間隔とマージし、残りの間隔を挿入します。 ただし、そうでない場合は、間隔の開始位置が挿入される間隔の開始位置よりも小さくなるまで、要素を出力ベクトルに挿入します。 次に、新しい間隔を挿入してから、残りの間隔を挿入するだけです。

コード

Insert Interval LeetcodeSolutionの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

Insert Interval LeetcodeSolutionのJavaコード

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要素を格納するベクトルの新しいベクトルを作成したためです。 スペースの複雑さも線形です。