[ leetcode 문제풀이 ] Merge Intervals

https://leetcode.com/problems/merge-intervals/

Merge Intervals - LeetCode

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

 

 

 

< Merge Intervals 문제 설명 >

 

Merge Intervals 문제는 다음과 같다.

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

 

intervals[i]가 구간 [starti, endi]인 주어진 intervals 배열에 대해 중첩되는 구간들을 모두 병합해 input으로 주어진 모든 구간을 나타내며 non-overlapping인 구간들의 배열을 리턴하여라.

 

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

 

 

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

1  ≤ intervals.length  ≤  10^4

intervals[i].length == 2

0  ≤  starti  ≤  endi  ≤ 10^4

 

 

 

---

< Merge Intervals 문제 접근 >

 

intervals 가 각 구간의 시작(starti)를 기준으로 오름차순 정렬되어있다고 하자. 이때 병합을 시도하는 구간의 index i에 대해서 j(j>i) index 구간이 중첩되는지 여부는 intervals[i][1] ≥ intervals[j][0] 인지를 확인하면 된다. 만약 구간이 중첩되지 않는다면 (intervals[i][1] < intervals[j][0]) j+1 ... index에 대해 intervals[i]와 중첩되는 interval은 존재하지 않는다.(∵intervals가 starti 기준으로 정렬되어 있으므로 !)

 

이와 같은 사실을 바탕으로 intervals[i]에서부터 i+1 ... 에 대해 위 탐색을 실시하고 중첩된다면 intervals[i]에 구간을 합병하는 과정을 누적한다. 만약 intervals[j]가 중첩되지 않는다면 병합을 시도하는 구간을 intervals[j]로 바꿔 반복한다.

 

이를 코드로 나타내면 다음과 같다.

 

#include <algorithm>

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    int n = intervals.size();
    if(n == 1) return intervals;

    sort(intervals.begin(), intervals.end());
    
    vector<int> start_idx;
    start_idx.push_back(0);
    for(int i=1;i<n;i++)
        if(intervals[start_idx.back()][1] >= intervals[i][0])
            intervals[start_idx.back()][1] = max(intervals[i][1], intervals[start_idx.back()][1]);
        else
            start_idx.push_back(i);
        
    int cnt = 0;
    while(!start_idx.empty()){
        intervals.erase(intervals.begin()+start_idx.back() + 1, intervals.end() - cnt++);
        start_idx.pop_back();
    }
    return intervals;
} // runtime : 28 ms (faster than 94.95 %), memory usage : 18.7 MB (less than 92.88 %)

 

for 반복문

 

→ start_idx : 중첩되는 interval을 포함하는 interval의 시작 위치(초기 intervals index 기준)

→ if문이 참 (↔ 중첩되는 구간 존재) - interval을 start_idx.back()(현재 갱신하고자 하는 구간의 시작 index) 위치에 갱신

→ if문이 거짓(↔ 현재 갱신하고 있는 구간 종료) - 다음 interval의 시작 위치 추가

 

while 반복문 : 갱신한 interval 외 필요없는 부분을 제거하는 과정

→ 지워야 하는 interval 집합은 start_idx의 원소의 개수만큼, 그 index를 기준으로 나뉘어 있음.

→ cnt : 지운 interval 토막의 개수

→ intervals.end() - cnt를 해주는 것은 지운 횟수만큼 partition역할을 하는 interval이 남아있게 되기 때문.

 

예시로 보자면 다음과 같이 동작하는 것이다.

example :

Input : intervals      = [[1,3], [2,6], [8,9], [3,10], [20, 23], [15,18]]

→ after sorting       = [[1,3], [2,6], [3,10], [8,9], [15,18], [20, 23]]

→ after for-loop     = [[1,10], [2,6], [3,10], [8,9], [15,18], [20, 23]] /start_idx = [0,4,5]

→ after while-loop = [[1,10], [15,18], [20, 23]] (answer)