c++ leet code medium merge_interval 구현

Merge interval은

{2,5}, {8,15}, {1,3}, {10,13}, {11,17} 과 같은 interval을

겹치는 구간은 병합하고, 분리된 부분은 분리하는 방법이다.

 

 

코드 >>

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
 
// merge_intervals
 
std::vector<std::vector<int>> merge_intervals(std::vector<std::vector<int>>& intervals)
{
    
    std::sort(intervals.begin(), intervals.end());
    std::vector<std::vector<int>> merged;
 
    for (const auto& interval : intervals)
    {
        if (merged.empty() || (merged.back()[1] < interval[0]))
        {
            merged.push_back(interval);
            std::cout << "interval merged" << std::endl;
        }
        else if ((merged.back()[1] < interval[1]))
        {
            merged.back()[1] = interval[1];
            std::cout << "interval back changed" << std::endl;
        }
    }
 
    return merged;    
}
 
int main()
{
    //input
    // [[1,3],[2,5],[8,15],[10,13],[11,17]]
    std::vector<std::vector<int>> nums;
    nums.emplace_back(std::vector<int> { 2,5 });
    nums.emplace_back(std::vector<int> { 8,15 });
    nums.emplace_back(std::vector<int> { 1,3 });
    nums.emplace_back(std::vector<int> { 10,13 });
    nums.emplace_back(std::vector<int> { 11,17 });
    
    std::vector<std::vector<int>> merged = merge_intervals(nums);
 
    for (int i = 0; i < merged.size(); i++)
    {
        std::cout << i << "th vector : { ";
        
        for (int j = 0; j < merged[i].size(); j++)
        {
            
            std::cout << merged[i][j] << ", ";
        }
        std::cout << " }" << std::endl;
    }
 
    return 0;
}