(Leet Code c++)Merge Intervals

56. Merge Intervals

 

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

 

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

 

주어진 intervals를 오름차순으로 정렬한다.

정렬을 한 후, front와 back을 intervals[0][0], intervals[0][1]로 초기값을 설정한 후 탐색 진행.

 

만약 back이 intervals[i][0]보다 작으면, 지금까지의 오버랩 된 수를 answer에 넣어준다.

그리고 front와 back을 intervals[i]에 있는 수로 저장.

 

그렇지 않고, back이 intervals[i][1]보다 작으면 back만 intervals[i][1]로 바꿔 오버랩을 진행한다.

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