[LeetCode] Merge Intervals

문제

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[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].

Example 2:

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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

 

Approach

우선 interval의 앞 원소 기준 오름차순으로 sort를 하고 시작한다. (custom sort function 필요)

그 다음 interval이 겹칠 조건을 생각해본다.

1. 지금까지 기록해 놓은 interval의 마지막보다 지금 본 interval의 시작이 크다 -> 안겹침. interval의 시작과 끝 갱신

2. 지금까지 기록해 놓은 interval의 마지막보다 지금 본 interval의 시작이 작다 -> 겹침

 - 2.1 지금까지 기록해 놓은 interval의 마지막보다 지금 본 interval의 마지막이 크다 -> interval의 마지막 갱신

이런 알고리즘으로 찾아나가면 된다. 시간복잡도는 O(nlogn)

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_MergeIntervals.cpp

chi3236/algorithm