[ leetcode ] 57. Insert Interval

start를 기준으로 오름차순으로 정렬된 겹치지 않는 구간 리스트가 주어졌을 때, 한 구간을 리스트에 삽입하는 문제입니다.

만약 삽입하는 과정에서 겹치는 구간이 발생하면 병합하여 하나의 구간을 만들어야 합니다.

 

Binary Search로 삽입할 index를 구하고, 해당 index를 기준으로 좌우로 two pointer로 넓혀가며 겹치는 구간을 찾고,

겹치는 구간이 있다면 삭제 후 병합한 새 구간을 넣어서 해결하였습니다.

 

#include <algorithm>

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>>::iterator insert_index = upper_bound(intervals.begin(), intervals.end(), newInterval);
        int i = insert_index - intervals.begin() - 1;  # 좌
        int j = i + 1;  # 우
        int size = intervals.size();
        bool overlap = false;
        
        while (i >= 0) {
            if (intervals[i][1] < newInterval[0]) break;
            overlap = true;
            i--;
        }
        while (j < size) {
        	if (intervals[j][0] > newInterval[1]) break;
            overlap = true;
            j++;
        }
        i++, j--;
        
        if (overlap) {
            newInterval[0] = intervals[i][0];
            newInterval[1] = max(intervals[j][1], newInterval[1]);
            intervals.erase(intervals.begin()+i, intervals.begin()+j+1);
            if (insert_index != intervals.begin() + i) insert_index--;
        }
        intervals.insert(insert_index, newInterval);
        return intervals;
    }
};