간격 Leetcode 솔루션 삽입-TutorialCup

Interval Leetcode Solution 삽입 문제는 일부 간격 목록과 별도의 간격 하나를 제공합니다. 그런 다음 간격 목록에이 새 간격을 삽입하라는 메시지가 표시됩니다. 따라서 새 간격은 이미 목록에있는 간격과 교차 할 수도 있고 그렇지 않을 수도 있습니다. 교차점이있는 경우 간격을 병합합니다. 그렇지 않으면 간격 목록의 오름차순을 따르는 위치에 삽입하기 만하면됩니다.

핀

차례

예

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

[[1,5],[6,9]]

설명 : 새 간격이 목록의 첫 번째 간격과 교차합니다. 따라서 새 간격은 첫 번째 간격과 병합됩니다. 그리고 그것이 우리가 주어진 출력을 남긴 방법입니다.

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

[0,5]

설명 : 처음에는 목록에 간격이 없었기 때문에. 우리는 단순히 새로운 간격을 삽입했습니다.

삽입 간격 Leetcode 솔루션에 대한 접근 방식

삽입 간격 Leetcode 솔루션 문제는 우리에게 삽입해야 할 간격과 추가 간격을 제공했습니다. 따라서 발생할 수있는 가능성을 시뮬레이션 할 수 있다면 문제를 해결할 수 있습니다. 새 간격이 이미 목록에있는 일부 간격과 교차하거나 교차하지 않는 두 가지 가능성이 있습니다. 그래서 만약 그렇다면 우리는 단순히 그것들을 병합하고 그렇지 않으면 간격을 특정 위치에 배치합니다. 특정 위치 란 삽입 후에도 목록의 오름차순이 유지됨을 의미합니다.

따라서이를 처리하기 위해 새 벡터 (정렬)의 벡터. 새로 생성 된 출력 벡터에 간격을 삽입하기 시작합니다. 현재 간격이 삽입 할 간격과 겹치는 지 확인합니다. 만약 그렇다면, 우리는 루프에서 벗어나게됩니다. 루프 후, 겹치는 요소가 목록에있는 간격에 있는지 확인합니다. 겹치는 경우 현재 간격을 새 간격과 병합하고 나머지 간격을 삽입합니다. 그러나 그렇지 않은 경우 간격의 시작 위치가 삽입 할 간격의 시작 위치보다 작을 때까지 요소를 출력 벡터에 삽입합니다. 그런 다음 새 간격을 삽입 한 다음 나머지 간격을 삽입합니다.

암호

삽입 간격 Leetcode 솔루션을위한 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

삽입 간격 Leetcode 솔루션을위한 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 요소를 저장하는 벡터의 새로운 벡터를 만들었 기 때문입니다. 공간 복잡성도 선형입니다.

예