-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
재귀 함수로 문제를 풀어봤습니다.
21.08.27 21:27 작성 조회수 114
0
function solution(arr) {
arr.sort((a, b) => {
if (a[0] === b[0]) return a[1] - b[1];
else a[0] - b[0];
});
function plan(idx, cnt) {
cnt++;
for (let i = idx + 1; i < arr.length; i++) {
if (arr[idx][1] <= arr[i][0]) cnt = Math.max(cnt, plan(i, cnt));
}
return cnt;
}
const answer = plan(0, 0);
return answer;
}
혹시 어디가 잘못된걸까요 ,,
답변을 작성해보세요.
0
사리곰탕
2021.10.09
안녕하세요 강사님!
저는 처음에 시작시간 기준으로 정렬을 해두고 검색하여 최대 회의 배정 개수를 찾아나가는 식으로 접근을 했는데요.
function solution(p) {
p.sort(([x1, y1], [x2, y2]) => (x1-x2) || (y1-y2) );
let answer = 0;
for(let i=0; i<p.length; i++) {
let [, le] = p[i];
let max = 1;
for(let j=i+1; j<p.length; j++) {
let [rs, re] = p[j];
if(le<=rs) {
max++;
le = re;
}
}
answer = Math.max(answer, max);
}
return answer;
}
이 문제를 보고 어떻게 종료시간 기준으로 정렬하여 그리디로 푸는 것이 답인지 아닌지에 대한 결정을 하는지 궁금합니다.
종료시간 기준하여 그리디로 풀었을때가 정답이 될 것이라다라는 논리가 어떻게 나오게 되는지 궁금합니다.
0
김태원
지식공유자2021.08.30
안녕하세요^^
그리디를 익히기 위한 문제이니 영상처럼 그리디로 푸는 것을 꼭 알아두시기 바랍니다.
아래는 반례입니다. 답은 5입니다.
console.log(solution([[1, 2], [2, 3], [3, 5], [6, 6], [7, 7]]));//5
답변 2