[ leetcode 문제풀이 ] Insert Interval

https://leetcode.com/problems/insert-interval/

Insert Interval - LeetCode

(Insert Interval 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Insert Interval 문제 설명 >

 

Insert Interval 문제는 다음과 같다.

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

 

intervals[i] = [starti, endi] 가 i번째 interval의 시작과 끝을 나타내도록 하는 non-overlapping 배열 intervals가 주어진다. (intervals는 starti를 기준으로 오름차순 정렬되어 있다) 또 다른 interval의 시작과 끝을 나타내는 newInterval = [start, end] 도 주어진다.

 

intervals가 여전히 starti를 기준으로 오름차순 정렬된 상태를 유지하며 non-overlapping을 만족하도록 newInterval을 삽입한다. (필요하다면 중첩되는 interval들은 합친다)

 

newInterval의 삽입 후의 intervals를 리턴하여라.

 

 

다음 두 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 다음과 같다:

0  ≤  intervals.length  ≤  10^4

intervals[i].length == 2

0  ≤  starti  ≤  endi  ≤  10^5

intervals is sorted by starti in ascending order.

newInterval.length == 2

0  ≤  start  ≤  end  ≤  10^5

 

 

 

---

< Insert Interval 문제 접근 >

 

intervals 가 starti를 기준으로 오름차순 정렬되어 있으며, starti  ≤  endi를 만족하므로 intervals를 1차원 vector로 생각한다면 intervals의 원소는 정렬된 상태라고 할 수 있다. 따라서, newInterval의 start와 end가 intervals의 어느 위치에 들어갈 수 있는지를 binary search 하면 newInterval이 intervals의 어떤 interval과 겹쳐 있는지, 얼마나 겹쳐있는지를 모두 알 수 있다.

 

이 idea를 바탕으로 작성한 알고리즘은 다음과 같다.

 

int binSearch(vector<vector<int>>& intervals, int new_val, int low, int high){
    if(low == high) return low;        
    int mid = (low + high) / 2;
       
    if(intervals[mid >> 1][mid & 1] > new_val)
        return binSearch(intervals, new_val, low, mid);
    else
        return binSearch(intervals, new_val, mid+1, high);
} // low -1 <= new_val < low 의 위치를 리턴함
    
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    int n = intervals.size();
    if(!n){
        intervals.push_back({newInterval}); 
        return intervals;
    } // intervals가 비어있는 경우 처리
    
    // intervals(1차원 vector로 생각)에서 newInterval[i]가 들어갈 위치 이진탐색
    int pos1 = binSearch(intervals, newInterval[0], 0, 2*n);
    int pos2 = binSearch(intervals, newInterval[1], 0, 2*n);
       
    // intervals와 겹치는 newInterval 구간을 newInterval에 덮어씌움
    if(!(pos1 & 1)){
        if(pos1 > 0 && intervals[(pos1-1) >> 1][1] == newInterval[0]){
            newInterval[0] = intervals[(pos1-1) >> 1][0];
            pos1--; // 겹치는 intervals의 시작 위치 재설정
        }
    }
    else    
        newInterval[0] = intervals[(pos1-1) >> 1][0];
        
    if(pos2 & 1) 
        newInterval[1] = intervals[pos2 >> 1][1];
 
    // intervals와 newInterval의 겹치는 interval을 제거한 후 수정한 newInterval을 insert
    intervals.erase(intervals.begin() + (pos1 >> 1), intervals.begin() + ((pos2+1) >> 1));
    intervals.insert(intervals.begin() + (pos1 >> 1), {newInterval});

    return intervals;
} // runtime : 16 ms (faster than 81.47 %), memory usage : 41.27 MB (less than 41.27 %)

 

알고리즘에서 정의한 binSearch는 intervals를 1차원 vector라 생각하고 newInterval[0]과 newInterval[1]이 어느 위치에 들어갈 수 있는지를 리턴하도록 하였다. intervals를 1차원으로 생각해 serarch하였을 때 알 수 있는 점은 찾아낸 위치(pos1, pos2)가 홀수 혹은 짝수 index인지에 따라 기존 구간과의 중첩 여부를 확인할 수 있다는 것이다. (pos1과 pos2는 중첩된 interval 들을 제거하기 위한 위치를 나타내는 역할을 한다.)

 

pos1이 짝수 index인 경우는 newInterval[0]이 중복되지 않는 interval의 시작이 되는 경우이다. 이때 추가적인 case를 고려해줘야 하는데, 바로 pos1-1 index의 value와 pos1 index의 value가 같은지이다. (같은 경우 interval을 합칠 수 있으므로) 따라서 이 경우는 pos1의 위치를 1만큼 왼쪽으로 이동시킨다. 반면, pos1이 홀수 index인 경우 newInterval이 구간과 중복되는 경우이므로 중복된 기존 구간을 합쳐 newInterval에 업데이트 한다.

 

pos2이 홀수 index인 경우 newInterval이 구간과 중복되는 경우이므로 중복된 기존 구간을 합쳐 newInterval에 업데이트 한다.
(pos2의 경우 짝수 index인 경우를 생각할 필요가 없는데, 이는 정의한 binSearch의 특성 때문이다. low-1 ≤ new_val  <  low 인 low를 리턴하기 때문에 newInterval[1]과 같은 값이 구간의 end로 있어도 newInterval이 구간을 닫는다는 사실은 변함이 없다.)

 

위의 pos1과 pos2 조건문으로 intervals와 newInterval의 구간 합병의 결과를 newInterval에 업데이트하였다.

 

이제 중첩되는 interval들을 모두 삭제해야 한다. pos1 >> 1의 결과는 중첩되는 interval의 시작 위치가 어디인지를 나타낸다.(ex1: pos1 = 5인 경우 pos1 >> 1 == 2 index의 interval부터 중첩이 시작됨, ex2: pos1 = 6인 경우 pos1 >> 1 == 3 index의 interval부터 중첩이 시작됨.)(pos2+1) >> 1의 결과는 중첩되는 interval의 끝 + 1 위치를 나타낸다. (ex1: pos2 = 9인 경우 (pos2 + 1) >> 1 == 5 index, ~4 index까지 interval의 중첩이 일어남. ex2: pos2 = 10인 경우 (pos2 + 1) >> 1 == 5 index, ~4 index까지 interval의 중첩이 일어남.)

 

구간을 삭제한 이후 중첩되는 interval의 시작점에 합병한 구간 newInterval을 집어넣으면 구하고자 하는 새로운 intervals이다.