[leetcode][435] Non-overlapping Intervals

문제 : https://leetcode.com/problems/non-overlapping-intervals/

---

interval 배열이 주어질 때 겹치지 않는 interval 요소들을 남기기위해 최소로 삭제해야 하는 interval 수를 구해라.

---

최소로 삭제해야 한다. = 가장 많은 interval들이 선택(삭제x)되어야한다.

정렬해서 푸는 그리디 문제이다.

끝 지점을 기준으로 오름차순 정렬시킨다. 끝 지점이 같다면 시작지점이 큰 순으로.(많은 interval 들이 선택되어야 하므로 interval이 작은것들먼저 선택되게 한다.)

선택된 interval들의 끝 지점을 last 변수에 저장한다.

정렬된 interval 배열을 앞에서부터 탐색하면서  탐색중인 interval의 시작지점이 last 변수보다 작다면 삭제되어야 한다.

예를 들어보자.

let) intervals = [[1,2],[2,3],[3,4],[1,3]]

정렬된 intervals = [[1,2],[2,3],[1,3],[3,4]]

[2,3] 탐색시 last 변수는 2일 것이다. 탐색중인 interval의 시작지점은 2이고 이는 last 변수인 2와 같으므로 이때까지 선택한 interval들과 겹치지 않을 것이다. (정렬했으므로 종료지점은 항상 이전보다 같거나 큰데 last 변수보다 시작지점도 크거나 같기 때문. = 겹치지 않음.)

1  2
   2  3 // 겹치지 않기 때문에 선택

[1,3] 탐색시 시작지점인 1은 last변수인 3보다 작다. 따라서 선택된 interval에 겹치는 범위이므로 선택하지 않고 삭제해준다.

1  2
   2  3
1     3 (범위 겹침 -> 삭제)

이와 같은 방법으로 모든 interval 변수를 탐색했을 때 삭제된 interval 수가 정답이 된다.

 

시간복잡도는 정렬하는데 드는 시간인 O(NlogN).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/435.%20Non-overlapping%20Intervals.cpp

---

 

sort(intervals.begin(), intervals.end(), [arr](vector<int>& a, vector<int>& b){} // #1
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){} // #2​

sort 함수 쓸 때 #1은 TLE나고 #2는 TLE가 발생안한다. [arr], [] 차이는 뭘까..

 

+ 그래서 스택오버플로우에 질문했봤따. 링크