리트코드 57 삽입간격 c++ // 구현, 라인스위핑은 케이스 분류하라

https://leetcode.com/problems/insert-interval/description/

1. 의사코드

이때, 핵심은 new를 탐색완료한것중 제일 우측의 간격으로 유지하는 점이다.

 

2. 전체코드

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ret;
        //new에는 현재 탐색완료한 간격중 제일 우측의 간격이 들어있다.
        for(auto interval : intervals){
            if(interval[1]<newInterval[0]){ //기존 < new 인경우
                ret.push_back(interval); //기존것은 그대로넣음, new를 어디넣어야될지 계속탐색
            }
            else if(newInterval[1]<interval[0]){ // new < 기존인경우 : 대부분 이경우임
                ret.push_back(newInterval); // new를 정답에 넣음
                newInterval = interval; //new 갱신
            }
            else{ //겹치는경우, 병합
                newInterval[0]=min(newInterval[0],interval[0]);
                newInterval[1]=max(newInterval[1],interval[1]);
            }
        }
        ret.push_back(newInterval); // 마지막남은거
        return ret;
    }
};

시간복잡도 : O(N) 추정