[인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 8. 회의실 배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.

 

풀이

function solution(meeting) {
  let answer = 1;
  let count, afterStart, end;

  meeting.sort((a, b) => {
    if (a[0] === b[0]) return a[1] - b[1];
    else return a[0] - b[0];
  });

  for (let i = 0; i < meeting.length; i++) {
    end = meeting[i][1];
    count = 1;
    for (let j = i; j < meeting.length - 1; j++) {
      afterStart = meeting[j + 1][0];
      if (afterStart >= end) {
        count++;
        end = meeting[j + 1][1];
      }
    }
    if (count > answer) answer = count;
  }

  return answer;
}

let arr = [
  [1, 4],
  [2, 3],
  [3, 5],
  [4, 6],
  [5, 7],
];
console.log(solution(arr));

먼저 시작하는 시각 기준으로 정렬하고, 끝나는 시각이 다음 시작하는 시간보다 작거나 같은게 있으면 카운트를 +1 해줬다. 모든 경우의 수를 하나하나 다 해봤다. 그 경우 중 가장 카운트 수가 많은게 정답이다. 비효율적인 풀이 같지만 이렇게밖에 생각이 안났다.

 

강사 풀이

function solution2(meeting) {
  let answer = 0;
  meeting.sort((a, b) => {
    if (a[1] === b[1]) return a[0] - b[0];
    else return a[1] - b[1];
  });
  let endtime = 0;
  for (let x of meeting) {
    if (x[0] >= endtime) {
      answer++;
      endtime = x[1];
    }
  }
  return answer;
}

let arr = [
  [1, 4],
  [2, 3],
  [3, 5],
  [4, 6],
  [5, 7],
];
console.log(solution2(arr));

회의를 가장 많이 할 수 있는 경우를 잡아야 하므로 해당 문제는 그리디 알고리즘으로 푸는 것이라 한다.
빨리 끝나는거 기준으로 정렬하고 만약 끝난 시간이 같다면 빨리 시작하는거 기준으로 정렬한다.끝나는거 기준으로 정렬하는걸 생각치 못했다. 이 방식이 훨씬 효율적인 것 같다.