[Leetcode] 56. Merge Intervals

문제 : https://leetcode.com/problems/merge-intervals/

---

간격 start, end 를 저장한 interval 배열이 주어질 때, 겹치는 모든 간격을 병합하여 간격이 겹치지 않게 만든 뒤 간격 배열을 반환하라.

---

intervals 배열을 start 오름차순으로 정렬한다.
start, end 변수를 만들고 겹치는 간격을 만나면 end 변수를 갱신해간다.
정렬한 배열을 앞에서부터 탐색하며 종료 간격 end가 탐색하는 간격의 start보다 같거나 크다면 합쳐질 수 있는 경우이므로 end를 갱신한다.
만일 그렇지 않다면 start, end를 정답 배열에 추가한다.

[[1,3],[2,6],[8,10],[15,18]] 예시

intervals[i]	start	end	answer 배열
[1,3]	1	3	[]
[2,6]	1	6	[]
[8,10]	8	10	[[1,6]]
[15,18]	15	18	[[1,6],[8,10]
종료			[[1,6],[8,10],[15,18]]

 

시간복잡도는 N = |intervals|,  O(NlogN)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/56.%20Merge%20Intervals.cpp