[JavaScript/section 7] 08 - 회의실 배정

📌 08 - 회의실 배정(그리디 알고리즘)

각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾는 문제이다. 단, 회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)이다.

👍 풀이 방법

그리디 알고리즘 문제는 정렬을 먼저 해야한다. 어떤 기준으로 정렬을 해야할까? 회의가 빨리 끝나야 뒤에 더 많은 기회가 생기므로 회의가 빨리 끝나는 순서대로  끝나는 시간이 같다면 위 조건(시작시간 <= 끝나는 시간)에 의해 회의가 빨리 시작하는 순서대로 정렬한다.

• 배열을 먼저 위 기준대로 정렬한다.
• 이전 회의 종료시간 endTime을 0으로 초기화한다.
• for 문을 돌면서 회의 시작시간이 이전 회의 종료시간보다 크거나 같다면(meeting[i][0]: 회의 시작 시간) answer++을 하고, endTime에 해당 회의의 종료시간을 저장한다.

 

📝 풀이

function solution(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 i = 0; i < meeting.length; i++) {
    if (meeting[i][0] >= endTime) {
      answer++;
      endTime = meeting[i][1];
    }
  }

  return answer;
}

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