재귀 함수로 문제를 풀어봤습니다.

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

8. 회의실 배정

작성

164

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;
}

혹시 어디가 잘못된걸까요 ,,

javascript 코테 준비 같이 해요!

답변 2

사리곰탕

안녕하세요 강사님!

저는 처음에 시작시간 기준으로 정렬을 해두고 검색하여 최대 회의 배정 개수를 찾아나가는 식으로 접근을 했는데요.

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;
}

이 문제를 보고 어떻게 종료시간 기준으로 정렬하여 그리디로 푸는 것이 답인지 아닌지에 대한 결정을 하는지 궁금합니다.

종료시간 기준하여 그리디로 풀었을때가 정답이 될 것이라다라는 논리가 어떻게 나오게 되는지 궁금합니다.

김태원

지식공유자

안녕하세요^^

그리디를 익히기 위한 문제이니 영상처럼 그리디로 푸는 것을 꼭 알아두시기 바랍니다.

아래는 반례입니다. 답은 5입니다.

console.log(solution([[1, 2], [2, 3], [3, 5], [6, 6], [7, 7]]));//5

인프런 커뮤니티 질문&답변

재귀 함수로 문제를 풀어봤습니다.