Merge Interval

• Reference
• Interval List들을 받아서, Merge 후 결과 Interval을 Return 한다.

Algorithm

[1, 5], [3, 7], [8, 16], [10, 15]

=> [1, 7], [8, 16]

• Interval Start 지점의 값을 기준으로 Sorting 후 merge를 해나가면 O(n)으로 해결할 수 있다.
  • 물론 Sorting이 필요한 경우에는 O(nlogn)이 소요된다.

[1, 5] [3, 7]

5 > 3

[1, 7]

• 2 번째 Interval의 첫 Range 값이 1 번째 Interval의 마지막 Range 값보다 작기 때문에 포함되는 것을 알 수 있다.
  • merge 시, 끝점을 5에서 7로 Update 하면 된다는 뜻이다.

[1, 7] [8, 16]

7 < 8

• 2 번째 Interval의 첫 Range 값이 이 1 번째 Interval의 마지막 Range 값 보다 크기 때문에 Merge가 안된다는 것을 안다.

[1, 7] [8, 16] [10, 15]

16 > 10

[1, 7] [8, 16]

• 2 번째 Interval의 첫 Range 값이 1 번째 Interval의 마지막 Range 값보다 작기 때문에 포함되는 것을 알 수 있다.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> mergeInterval(const std::vector<int> &v1, const std::vector<int> &v2)
{
    std::vector<int> mergedInterval;

    if (v1[1] > v2[0])
    {
        mergedInterval.emplace_back(v1[0]);
        mergedInterval.emplace_back(v2[1]);
    }

    return mergedInterval;
}

int main()
{
    std::vector<std::vector<int>> v = {{1, 5}, {8, 16}, {3, 7}, {10, 15}};
    sort(v.begin(), v.end(), [](std::vector<int> &v1, std::vector<int> &v2) -> bool
         { if (v1[0] < v2[0]) return true; else return false; });

    std::vector<int> v1 = v[0];
    std::vector<int> v2;
    std::vector<int> mergedVector;
    std::vector<std::vector<int>> resultVector;
    v2.reserve(2);
    mergedVector.reserve(2);
    for (int idx = 1; idx < v.size(); ++idx)
    {
        v2 = v[idx];
        mergedVector = mergeInterval(v1, v2);

        if (!mergedVector.empty())
        {
            v1 = mergedVector;
        }
        else
        {
            resultVector.emplace_back(v1);
            v1 = v2;
        }
    }

    if (!resultVector.empty())
        resultVector.emplace_back(mergedVector);

    for (auto vec : resultVector)
    {
        std::cout << "{";
        for (auto e : vec)
        {
            std::cout << " " << e << " ";
        }
        std::cout << "}," << std::endl;
    }
    return 0;
}

{ 1  7 },
{ 8  15 },