[c++/LeetCode-Array] 56. Merge Intervals

 

난이도: Medium

키워드: Array

 

 

문제

 

문제원문: https://leetcode.com/problems/merge-intervals/description/

주어진 간격 배열에서, intervals[i] = [starti, endi]인 간격들이 있을 때, 겹치는 모든 간격을 병합하고, 입력된 모든 간격을 포괄하는 겹치지 않는 간격들의 배열을 반환하시오.

 

문제 풀이

 

겹치는 구간들을 합쳐주기위해서, intervals 를 start time 기준으로 sorting하고 merge를 진행한다. 그러면 sort는 O(n log n)이 보장되고, sorting 된 array에 대해서 merge만 해주면 되므로 O(n). 최종적으로 O(n log n) 복잡도로 해결.

 

#include <algorithm>
#include <vector>

using namespace std;

bool compare(const vector<int>& left, const vector<int>& right){
    return left[0] < right[0];
};
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        vector<vector<int>> ans;

        for(auto interval: intervals){
            if(ans.size() > 0 && interval[0] <= ans[ans.size()-1][1]){
                ans[ans.size()-1][1] = max(interval[1], ans[ans.size()-1][1]);
            } else {
                ans.emplace_back(interval);
            }
        }
        return ans;
    }
};