C++2 [leetcode][435] Non-overlapping Intervals 문제 : https://leetcode.com/problems/non-overlapping-intervals/ interval 배열이 주어질 때 겹치지 않는 interval 요소들을 남기기위해 최소로 삭제해야 하는 interval 수를 구해라. 최소로 삭제해야 한다. = 가장 많은 interval들이 선택(삭제x)되어야한다. 정렬해서 푸는 그리디 문제이다. 끝 지점을 기준으로 오름차순 정렬시킨다. 끝 지점이 같다면 시작지점이 큰 순으로.(많은 interval 들이 선택되어야 하므로 interval이 작은것들먼저 선택되게 한다.) 선택된 interval들의 끝 지점을 last 변수에 저장한다. 정렬된 interval 배열을 앞에서부터 탐색하면서 탐색중인 interval의 시작지점이 last 변수보다 작다면.. 2020. 8. 16. [C++] STL pair를 sort 함수로 내림차순 정렬하기 sort 함수를 알고리즘 문제를 풀다가 정렬할 때 마다 쓰는데 내림차순을 원하거나 second 값으로 오름차순을 하길 원할 때 compare 함수를 어떻게 짜야하는지 맨날 헷갈린다. 그래서 포스팅해둠. sort 함수는 algorithm 헤더파일을 필요로 한다. sort(시작 주소, 종료 주소, [비교함수]) 비교함수는 생략이 가능하다. 생략시에는 오름차순으로 정렬된다. sort 함수 compare 함수대신 greater(), less(int>() 들도 사용한다고 하는데 아직 한 번도 안 써봤다... 이 때, sort(&arr[0], &arr[N], compare); 이렇게 써주어도 된다. 정렬되는 범위가 시작 주소는 포함하고 종료 주소는 포함이 되지 않는다고 한다. 즉, 위 함수 정렬의 범위는 ar.. 2019. 5. 31. 이전 1 다음
