leetcode_57.cpp

class Solution {
    public:
        vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
            vector<vector<int>> result;
            int i = 0, n = intervals.size();
            
            // 1. newInterval보다 완전히 왼쪽에 있는 구간들 추가
            while (i < n && intervals[i][1] < newInterval[0]) {
                result.push_back(intervals[i]);
                i++;
            }
            
            // 2. 겹치는 구간들을 병합
            while (i < n && intervals[i][0] <= newInterval[1]) {
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
                i++;
            }
            result.push_back(newInterval);
            
            // 3. newInterval보다 완전히 오른쪽에 있는 구간들 추가
            while (i < n) {
                result.push_back(intervals[i]);
                i++;
            }
            
            return result;
        }
    };