LeetCode 56. Merge Intervals

문제

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

걸린 시간

-

풀이

C++

#define MAX 1e4+1

struct link{
    bool left, right, mid;
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        vector<link> array(MAX, {false, false, false});
        for(vector<int> i : intervals){
            if(i[0] == i[1]){
                array[i[0]].mid = true;
                continue;
            }
            array[i[0]].right = true;
            for(int j = i[0]+1; j < i[1]; j++){
                array[j].left = array[j].right = true;
            }
            array[i[1]].left = true;
        }
        vector<int> tmp;
        for(int i = 0; i < MAX; i++){
            if(array[i].left && !array[i].right) tmp.push_back(i);
            if(!array[i].left && array[i].right) tmp.push_back(i);
            if(array[i].mid && !array[i].left && !array[i].right){
                tmp.push_back(i);
                tmp.push_back(i);
            }
        }
        for(int i = 0; i < tmp.size(); i+=2)
            ans.push_back({tmp[i], tmp[i+1]});
        return ans;
    }
};

정렬 문제인 것 같은데 다른 방법으로 풀이했다.

연결 정보를 구조체로 관리하여 중복된 구간들을 하나로 합쳤다.