[Leetcode] 57. Insert Interval

Identifying the Problem

범위를 나타내는 2개의 열로 이뤄진 interval 배열에 new interval을 삽입해 바뀐 interval을 리턴한다.

 

Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]

Explanation: [1,3] 과 [2,5]가 겹치므로 [1,5] 로 바꾸어 준다.

 

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]]

Explanation: [4,8] 이 [3,5],[6,7],[8,10]와 겹쳐 [3,10] 으로 합쳐졌다..

Organizing thoughts

규칙을 최대한 찾아보았다.

1. interval과 new의 요소 개수는 짝수 개

2. output은 행의 개수를 최소화 시키는 게 아니라, 영향을 준 부분만 수정한다.

3. 더 깊이 생각해보면 영향을 안준 부분은 output에 그대로 내보내면 된다.

4. 오름차순이라는 점을 이용한다.

5. 영향을 준 부분을 output에 보내는 방법을 생각해보자

    a. new의 범위는 최대 [0, interval의 최대 보다 큰 값] 최소 [n, n+1]

    b. new의 요소가 interval 내에 들어가면 범위를 변경해야 한다.

6. new가 들어갈 곳이 아무 곳도 없는 경우

    a. new의 end 부분이 interval의 처음 값 보다 작다면, 최우선에 insert한다.

    b. new의 start 부분이 interval의 마지막 값 보다 크다면, 마지막 부분에 insert한다. 

 

[전체적인 flow]

<second < new_start> 일 때는 정답에 추가하다가

<new_end 가 들어갈 위치를 찾으면> new_start ~ new_end 의 범위에 맞게 정답에 추가 후

<이후> 나머지를 그대로 넣으면 된다.

Sourcecode

#직접 작성한 코드

interval의 size가 1인 경우 및 다른 특정한 경우 올바르게 작동하지 않는다.

다행히 정답 코드와 전체적인 flow는 유사했다.

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans(intervals.size()+1,2);
        int start = newInterval[0];
        int end = newInterval[1];
        int flag = 0; //new의 범위를 설정하고, 탐색하는 부분이 되면 flag를 올린다.
        
        if(end > interval[0][0])
        {
            interval.push_front(newInterval);
            return interval;
        }
        if(start > interval[interval.end()][1])
        {
            interval.push_back(newInterval);
            return interval;
        }
        int k = 0;
        for(int i=0; i<interval.size(); i++)
        {
            if(interval[i][0] <= start && start <= interval[i][1])
            {
                start = interval[i][0];
                flag = 1;
            }
            else if(start < interval[i][0])
                flag  = 1;
            
            if(flag == 0)
                ans[k++] = interval[i];
            
            if(interval[i][0] <= end && end <= interval[i][1])
            {
                end = interval[i][1];
                ans[k][0] = start;
                ans[k][1] = end;
                flag = 0;
                k++;
            }
            else if(end < interval[i][0])
            {
                ans[k][0] = start;
                ans[k][1] = end;
                flag = 0;
                k++
                ans[k] = interval[i];
            }
        }
        
        return ans;        
    }
};

# 정답 코드 및 코드 출처

Hard Problem? C++ Easy Solution - LeetCode Discuss

 

class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& ints, vector<int>& ni, int i = 0) {
    vector<vector<int>> res;
    
    for (; i < ints.size() && ints[i][0] <= ni[1]; ++i) 
    {
    //i를 끝까지 탐색하되, new의 end가 가능한 범위 내에서 진행한다.
    //만약 interval[i][0]가 6인데 end 부분이 4면 범위를 벗어난 것이다.
    //즉 new가 해당하는 범위를 탐색함과 동시에 new의 이전 범위를 추가하는 작업이라 생각하면 된다.
   
        if (ints[i][1] < ni[0]) //new의 범위 이전에 interval이 있으면
            res.push_back(ints[i]); //정답 배열에 interval 추가
        else 
            //탐색 중인 interval이 new 범위 안에 들어왔다면, 
            //첫 else에서 start가 결정되고, 마지막 else에서 end가 결정
        {
            ni[0] = min(ni[0], ints[i][0]);
            ni[1] = max(ni[1], ints[i][1]);
        }
        //else 의 의미를 더 생각해보자면,
        //interval[i][0] <= new_interval[1] : new의 end가 가능한 범위
        //interval[i][1] >= new_interval[0] : interval 값이 new의 start를 넘어야 new의 범위 안에 들어온 것
    }
    
    res.push_back(ni); //정해진 start와 end 범위를 삽입
    res.insert(end(res), begin(ints) + i, end(ints)); //end 이후 남아 있는 interval 요소들을 삽입한다.
    return res; 
   
    }
};