LeetCode : 57. Insert Interval

중첩된 범위를 가지는 부분을 하나로 합쳐주는 문제였다.

 

[메인 로직]

가장 핵심 부분이, 만약 [Start, End]로 구성된 배열이 있을 때, End값보다 작거나 같은 Start값을 갖는 또 다른 배열이 있다면

2개의 배열을 합쳐서 하나의 배열로 만들 수 있다.

ex) [2, 4], [3, 6]이라면 4>=3이기 때문에 [2, 6]으로 만들 수 있다.

또한, [2, 5], [3, 4] => [2, 5]이기 때문에 합쳐진 후의 End값은 두 배열의 End값중 큰 값으로 정해지는 것도 고려해야 한다! (내가 틀렸던 부분...^^)

 

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end());
        
        vector<vector<int>> ans;
        for(int i=0; i<intervals.size(); i++){
           int Start = intervals[i][0];
           int End = intervals[i][1];
            bool check = false;
 
            for(int j=0; j<ans.size(); j++){
                if(ans[j][1]>=Start){
                    check = true;
                    if(ans[j][1]<End){
                        ans[j][1] = End;
                    }
                    break;
                }
            }
            
            if(check==false){
                vector<int> temp;
                temp.push_back(Start);
                temp.push_back(End);
                ans.push_back(temp);
            }
        }
        
        return ans;
    }
};