Leetcode - 57. Insert Interval

문제

서로 겹치지 않는 [시작, 종료] interval 들이 담긴 배열이 주어진다. 새로운 interval이 들어왔을때, 중첩되는 interval을 합쳐서 배열을 다시 구성해라.

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

해결

중첩이 발생하기 전, 그리고 발행 이후는 순서대로 push하고, 중첩부분에서 시작 값중 가장 작은 값과 종료값중 가장 큰값을 push하면 된다.

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int isize = intervals.size();
        vector<vector<int>> ret;
        int remains;
        vector<int> tmp(2,0);
        tmp[0] = newInterval[0];
        tmp[1] = newInterval[1];
        
        for (int i = 0; i < isize; i++) {    
            if (intervals[i][1] < newInterval[0]) {
                ret.push_back(intervals[i]);
            } else if (newInterval[1] < intervals[i][0]) {
                remains = i;
                break;
            } else {
                tmp[0] = std::min(intervals[i][0], tmp[0]);
                tmp[1] = std::max(intervals[i][1], tmp[1]);
            }
        }
        ret.push_back(tmp);
        for (int i = remains; i < isize; i++)
            ret.push_back(intervals[i]);
        return ret;
    }
};