[알고리즘] Merge Intervals (LeetCode 56)

문제 : [start, end] 형태의 여러 개의 interval이 주어졌을 때, 그 interval 들의 합집합을 계산하라.

 

아이디어 1. 주어진 순서대로 자신 이후의 interval들과 비교하여 (정확히는 자신의 end와 비교대상의 start, end가 더 크면 겹치는 부분 존재) 합집합을 계산. 

예상 시간복잡도 : (n-1)+(n-2)+...+1 = n(n-1)/2,   O(n^2)

 

아이디어 2. 주어진 interval들을 start에 대해 정렬한다. 이후 위 아이디어처럼 하나씩 비교하다가 겹치지 않는 interval (K)이 발견되는 K 이후 interval들의 start가 최소 K의 start보다 크므로 더 이상 비교할 필요 없어지고, K 이하의 interval 들은 건너뛰고 비교 기준을 바로 K로 설정한 뒤 프로세스를 반복한다.

예상 시간복잡도 : 정렬에 O(nlog(n)), 위 과정처럼 비교가 이루어지면 n-1번의 비교 (O(n))가 이루어지므로 총 O(nlog(n))

 

(memo)

- 배열 같은 자료구조에서 순서대로 비교하여 O(n^2) 의 시간복잡도가 나오는 알고리즘을 정렬을 통해 O(nlog(n))으로 줄일 수 있는지 생각해볼 수 있다.

- C++ algorithm 라이브러리의 sort()로 벡터를 O(nlog(n)) 시간 내에 손쉽게 정렬할 수 있다. 정렬하고 싶은 벡터의 start와 end iterator를 인자로 받는다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> MergeIntervals(vector<vector<int>> &arr) {

    vector<vector<int>> result;
    // comparing each vectors in given sequence makes O(n^2) time complexity
    // we can sort with the first element of each vector by O(nlogn) time, then merge in O(n) time, hence O(nlogn) for whole algorithms.

    // Merge Sort (O(nlogn), stable sort)
    sort(arr.begin(),arr.end());

    // Two pointers : current, compare AND one iMax = current[1]
    // if current[1] >= compare[0] => update iMax <- max(iMax, compare[1]), and then compare++
    // if current[1] <  compare[0] => no merge after this (including this), hence current <- compare++
    result.push_back(arr[0]);
    int current = 0;
    int iMax = result[current][1];

    // O(n) comparison.
    for (int compare = 1; compare<arr.size(); ++compare)
    {
        // End of Comparing Standard > Start of Compared Interval (have intersection)
        if (iMax >= arr[compare][0])
        {
            result[current][0] = min(result[current][0],arr[compare][0]);
            result[current][1] = max(result[current][1],arr[compare][1]);
        }
        else // No intersection
        {
            result.push_back(arr[compare]);
            current++;
        }
    }
    
    return result;
}



int main() {
    vector<vector<int>> arr = {{1,3},{2,6},{8,10},{15,18}};
    vector<vector<int>> result = MergeIntervals(arr);
    for (int i =0; i<result.size(); i++)
    {
        cout << result[i][0] << " " << result[i][1] <<endl;
    }
    return 0;
}

// 출력 결과
// 1 6
// 8 10
// 15 18