leetcode 56. merge-intervals [c++] [point :이차원벡터 정렬]

leetcode 56. merge-intervals 해설 

 

원본 문제 : 

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

 

문제해석요약 : 아래처럼 범위가 겹쳐지는게 있으면 합쳐서 하나로 만들어라

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

Check Point 

1. 데이터 타입 : 이차원 벡터

2. 배열내 원소를 합치기 위한 기본 로직 :

    i번째 원소의 end가  i+1번째 원소의 start보다 크면 겹치게 된다. 

    [1,3] , [2,5] -> 3이 2보다 크므로, 범위가 겹친다. 

3. 기본로직을 보장하기 위한 필요조건 : 

    2차원 벡터가 정렬되어있어야한다.  ( 그래야 크기비교를 제대로 할 수 있음) 

4.  구현 유의사항 

     원본 데이터(intervals)를 변형시키는것보다 2번의 기본로직 수행후 새로운 배열에 담는게 더 쉽다. 

 

 

단순한 문제였지만, sort 부분에서 다음 내용을 알고 넘어가면 좋다. 

1. 벡터의 정렬 

일차원 벡터의 정렬 : sort(arr.begin(),arr.end()); 

2. 이차원 벡터 정렬 :

1) sort(arr.begin(),arr.end()) 로 정렬 할 경우, arr[0][0],arr[1][0] 값을 비교한다. 

2) 비교로직 수정 : 사용자 지정 비교함수 cmp를 선언한다. 

bool cmp(vector<int> a, vector<int> b) {
  return (a.size() < b.size());	//a, b의 size로 정렬 , 작은게 앞으로
  // return (a[i],b[i]);	// i 번째 요소로 정렬, 모든 원소가 갖고있어야함.
}
sort(arr.begin(),arr.end(), cmp)	//사용법

Source Code

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;  // 반환값
        sort(intervals.begin(), intervals.end());  // 이차원 벡터의 정렬
        result.push_back(intervals[0]);  // 맨처음껀 결과 값에 한번 넣어주고
 					 // 그 다음값부터 비교시작한다. 
        int j=0;
        for(int i=1; i< intervals.size(); i++){
        // 기본 로직부분, max를 쓰는 이유는,
        // intervals[i][1],result[j][1]의 두값중 큰값을 end값으로 사용하기 위해서다.
            if(result[j][1] >= intervals[i][0]) result[j][1] = max(intervals[i][1],result[j][1]); 
            else{
            	//겹치지 않을경우 그냥 삽입함. 
                result.push_back(intervals[i]);
                j++;
            }
        }     
        return result;        
    }
};