Leetcode - 56. Merge Intervals

문제

intervals[i] = [starti, endi] 로 interval이 주어진다. 겹치는 부분을 합쳐라. (참고로 interval[]는 정렬되어있지 않음)

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] overlap, merge them into [1,6].

해결 O(n)

greedy한 방식으로 첫번째 값과 interval을 비교하면서 겹치면 확장. 안겹치면 push하고 그 값과 다음 interval을 비교한다.

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