[C++] LeetCode : Merge Interval

Question

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.

 

구간의 시작점과 끝점 정보가 담긴 배열들을 담고있는 배열이 주어졌을 때, 겹치는 구간을 모두 합쳐, 겹치는 구간이 없게  반환하라. 

 

제약사항

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

---

Solution

문제를 풀면서 고려한 사항

• [1,2] , [2,3] 두 구간이 주어졌을 때 [1,3] 이 합쳐져야 한다. 
• [1,2] , [3,4] 는 연속된 구간이 아니다. 

구간을 전부 점으로 찍는다고 생각하고, 점이 찍힌 구간을 연속된 구간이라고 판단하는 방법은 오류가 있다.
예를 들어 [1,3] [4,5] 구간일 때 
1 2 3 이 찍히고 4 와 5가 찍혀 1,5를 연속된 구간이라 판단할 수 있지만, 아니기 때문에 다른 방법이 필요하다

가장 쉬운방법을 생각해보자.

---

Solution1 (Bruth Force)

새로운 구간이 입력될 때마다 각 구간에 겹치는 부분이 있다면 갱신해주는 방식을 생각해보자
예로 주어진 [[1,3],[2,6],[8,10],[15,18]] 구간에서 

[1,3] : 첫 행 입력으로 바로 넣어줌
[2,6] : [1,3] 과 비교 후 겹치기 때문에 갱신 [1,6]
[8,10] : [1,6] 과 비교 후 겹치지 않기 때문에 넣어줌
[15,18] : [1,6] 및 [8,10]과 비교 후 겹치지 않기 때문에 넣어줌.

이런 방식이라면, 주어진 구간의 개수가 N일 때 비교에 N * N-1 * N-2 = O(N!)이다. 
이 방식은 주의할 점이, 원래 겹치는 구간이 없었던 구간들이, 갱신 후 겹쳐질 수 있기 때문이다. 그 부분까지 고려를 해야 한다. 

Solution2

하지만 만약 주어진 구간이 시작점을 기준으로 정렬된 구간이라고 가정을 한다면, 겹치는 작업을 해줄 때 갱신 후 겹쳐질 걱정은 하지 않아도 된다.
또한 정렬되어 있기 때문에 모든 구간을 기준으로 검색 하기 보다 마지막 구간을 기준으로 작업을 해주면 된다. 

 

예를 들어 아래와 같이 구간이 주어졌다고 한다면 
[1,9], [2,5], [19,20], [10,11], [12,20], [0,3] [0,1] [0,2] 

이를 start를 기준으로 정렬 한다면 아래와 같이 된다. 
[0,3] [0,1] [0,2] [1,9], [2,5] [10,11] [12,20] , [19,20]

이 구간을 기준으로 합쳐주는 작업을 해주면 위의 고려사항들을 고려하지 않아도 된다.

[0,3] <- [0,3]
[0,3] <- [0,1]
[0,3] <- [0,2]
[0,9] <- [1,9]
[0,9] <- [2,5]
[0,9],[10,11] <- [10,11]
[0,9], [10,11], [12,20] <- [12,20]
[0,9], [10,11], [12,20], [19,20] <- [19,20]

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> merged;
		
		sort(intervals.begin(), intervals.end());
		
		for(auto interval : intervals){
			if(merged.empty() || merged.back()[1] < interval[0]){
				merged.push_back(interval);
			}
			
			else{
				merged.back()[1] = max(merged.back()[1], interval[1]);
			}
		}
		
		return merged;
    }
};

시간 복잡도는 정렬을 위한 시간복잡도 O(nlogn) + interval 순회를 위한 O(n) 합쳐서 O(nlogn)이다.

• Time complexity : O(nlogn) , 정렬을 위한 시간 복잡도 O(nlogn) + interval 순회를 위한 O(n)
• Space Complexity : O(logn), 정렬을 in- place에서 할 수 있다면 O(1)이다. 

출처 : https://leetcode.com/problems/merge-intervals/

Merge Intervals - LeetCode