[Leetcode] 56. Merge Intervals

Identifying the Problem

시작과 끝의 간격이 주어져 있는 2차원 배열의 겹치는 부분을 최소화하여 리턴한다.

 

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]

Explanation: [1,3] 과 [2,6] 겹치므로, [1,6]으로 합침

 

Input: intervals = [[1,4],[4,5]] Output: [[1,5]]

Explanation: [1,4] 과 [4,5] 4가 겹치므로 [1,5]로 합침

Organizing thoughts

1. intervals 배열 정렬된 상태가 아니기에, 시작점이 작은 순서대로 정렬한다.

2. 초기 interval 2쌍을 초기 시작과 끝 값으로 대입하고, 다음 interval과 비교를 시작한다.  
3. intervals만큼 반복문을 진행하며 시작점과 기준값의 종료점을 비교하고 정한다.  

3. 시작과 끝을 정하는 과정

  a) 끝이 탐색 값의 시작 값 보다 더 크거나 같은 경우
     범위가 겹치는 경우이므로 start는 최소값 end는 최댓값으로 설정하고

     정답에 추가한다.

     여기서 주의할 점은 연속해서 겹치는 경우

     정답을 추가해주는 것이 아니라, 바뀐 start와 end를 업데이트 해준다고 봐야 한다.

     따라서 이 때는 이전에 추가한 배열을 지워준다.


  b) 그 반대의 경우
  겹치지 않는 경우이므로, 탐색하는 interval을 그대로 추가한다.

 

4. 정해진 시작 값과 끝 값을 정답에 추가한다.

Sourcecode

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans; //정답 배열
        vector<int> merge; //처음 값과 끝 값을 저장할 배열
        sort(begin(intervals), end(intervals)); //첫 값 기준 오름차순 정렬
        
        ans.push_back(intervals[0]); //초기값 설정
        
        merge.push_back(intervals[0][0]); //초기 start
        merge.push_back(intervals[0][1]); //초기 end
         
       
        
        
        for(int k = 0 , int i=1; i<intervals.size();i++)
        {
            if(merge[1] >= intervals[i][0]) //겹친 경우
            {    
                ans.erase(ans.begin()+k); //기존 겹친 경우를 지워주고
                merge[1] = max(intervals[i][1],merge[1]);
                merge[0] = min(intervals[i][0],merge[0]);
            }   
            else //안 겹친 경우
            {
                merge[0] = intervals[i][0]; //그대로 진행
                merge[1] = intervals[i][1];
                k++; //ans의 index 증가
            }
                
                
            ans.push_back(merge);  //결정된 처음과 끝 추가
        }
        
        
        return ans;
    }
};