[ leetcode ] 56. Merge Intervals

여러 구간들이 주어졌을 때, 겹치는 구간을 병합하여 겹치지 않는 구간들의 리스트를 반환하는 문제입니다.

먼저 구간들을 오름차순으로 정렬하고, 정답 리스트에 구간을 하나 추가하고 마지막 추가된 구간과 새로 들어갈 구간들이 겹치는지 판단하여 겹치는 경우 마지막 구간을 빼서 병합하고 다시 넣어주는 과정을 반복합니다.

#include <algorithm>
#define max(a,b)((a) > (b) ? (a) : (b))

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
    	sort(intervals.begin(), intervals.end());
        vector<vector<int>> answer;
        
        for (int i = 0; i < intervals.size(); i++) {
        	int start = intervals[i][0];
        	int end = intervals[i][1];
            if (answer.size()) {
            	if (answer[answer.size()-1][1] >= start) {
                    vector<int> item = answer.back();
                    answer.pop_back();
                    start = item[0];
                    end = max(end, item[1]);
                }
            }
            answer.push_back(vector<int>{start, end});
        }
        return answer;
    }
};