[leetcode][1288] Remove Covered Intervals

문제 : https://leetcode.com/problems/remove-covered-intervals/

---

간격배열이 주어질 때, [a,b), [c,d)가 있는 경우 c <= a, b <= d 라면 [a,b)는 [c,d) 범위에 포함된다.

포함되는 간격들을 모두 삭제하고 남은 간격들의 수를 구하는 문제다.

---

intervals 배열을 intervals[i][0]은 오름차순으로 만약 intervals[i][0]이 같다면 intervals[i][1]은 내림차순으로 정렬한다.

예를 들어, intervals = [[1,4],[3,6],[2,8],[2,4]]라 하자.

이를 아까 말한 방법때문에 정렬한다면 [[1,4],[2,4],[2,8],[3,6]]가 된다.

이제 포함되는 조건들 중 c <= a는 반드시 충족되기 때문에, 2번째 조건인 b <= d만 판단하면 된다.

앞에서부터 탐색하면서 intervals[i][1]의 최대값을 last 변수에 저장한다.

만약 intervals[i][1](b) <= last(d) 인 경우 2번째 조건도 충족하기 때문에 탐색중인 intervals[i]는 삭제가능하다.

모든 intervals를 탐색하면서 삭제가능한 간격들(delCnt)의 개수를 구한다음 intervals 사이즈에서 delCnt를 빼면 정답이 된다.

 

시간복잡도는 intervals 배열을 정렬하는데 걸리는 시간인 O(NlogN)이다.

---

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