[LeetCode] 57. Insert Interval

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

Leetcode - Insert Interval

문제 유형 : 배열, 구현

문제 난이도 : Medium

 

문제

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

 

당신은 겹치지 않는 배열 intervals를 받습니다. 

intervals는 [start, end]의 배열형식으로 되어 있습니다. 각각 겹치는 부분 없이 오름차순으로 되어있습니다.

newInterval도 [start, end]꼴로 있습니다.

newInterval을 삽입하여 기존 규칙을 유지하도록 하여 반환하시오. 다른 인터벌과 겹치는 부분을 병합할 수 있습니다.

Note: 새로 배열을 만들어서 반환해도 됩니다.

 

풀이

우선, 새로운 반환용 배열을 만든다.

newInterval[0]보다 intervals[i][1]이 작은 동안 intervals[i]를 계속 삽입한다.

 

이제, newInterval을 넣을 차례인데, newInterval과 겹치는 부분이 있는 요소들과 하나로 병합해준다.

그 뒤, 반환용 배열에 삽입한다.

 

나머지 intervals요소들을 순차적으로 넣는다. 그 뒤 반환하면 된다.

 

코드

C++

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int i = 0;
        int n = intervals.size();
        vector<vector<int>> ans;

        while(i < n && intervals[i][1] < newInterval[0]) {
            ans.push_back(intervals[i]);
            i++;
        }

        while(i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        ans.push_back(newInterval);

        while(i < n) {
            ans.push_back(intervals[i]);
            i++;
        }

        return ans;
    }
};