[leetcode 56] Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

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.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

 

Constraints:

• intervals[i][0] <= intervals[i][1]

문제 풀이:

1. 일단 소팅. 각 벡터의 0행렬을 기준으로 오름차순 소팅한다.

2. 다른 벡터들을 돌면서 다른 벡터의 1값과 비교하여 end 값을 업데이트 한다.

class Solution {
public:
    static bool compare(vector<int>& a, vector<int>& b){
        if(a[0] == b[0]){
            return a[1] <b[1];
        }
        
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
     
        vector<vector<int>> result;
        
        sort(intervals.begin(), intervals.end(), compare);
        
        int len = intervals.size();
        if(len == 0){
            return result;
        }
        
        for(int i=0; i<len; i++){

            int start = intervals[i][0];
            int end = intervals[i][1];
            
            while(i+1<len && end >= intervals[i+1][0]){
                i++;
                end = end > intervals[i][1]? end: intervals[i][1];
            }
            
            result.push_back({start, end});
        }
        return result;
    }
};