[그리디]회의실 배정

문제

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

 

문제풀이

1. 시작 시간을 기준으로 순차 탐색을 돌아야하기 때문에 오름차순으로 자료구조를 정렬_ 시작시간과 종료시간이 같을 경우도 있기 때문
2. 현재 참조하고 있는 회의 종료시간보다 회의 시작시간이 같거나 클 경우 회의 가능
3. 회의가 가능한 회의 시작시간을 그 다음 종료시간으로 변경

코드

function solution(...arr) {
  let answer = 0;
  arr.sort((a, b) => a[0] - b[0]); //회의 시작 시간 기준으로 오름차순 정렬

  for(let i = 0; i < arr.length; i++) {
    let tmp = arr[i][1]; //회의 종료시간
    let count = 1;
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[j][0] >= tmp) { //회의가 이전 회의가 종료된 시간대일 경우
        tmp = arr[j][1]; //회의 종료시간 변경
        count++;
      }
    }
    answer = Math.max(answer, count);
  }
  
  return answer;
}

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

 

오답

탐욕(그리디) 알고리즘(Greedy algorithm)

• 최적해를 구하는 상황에서 사용하는 방법
• 여러 경우 중 하나를 선택할 때 그것이 그 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식
• 가장 좋은 결과를 얻는 것이 보장되는 것은 아님

---

가장 많은 회의를 해야되는 상황 속에서 위의 문제 풀이와 같이 시작 시간을 정렬 기준으로 삼게 된다면 다음 그림과 같은 문제가 생긴다.

시작시간 및 회의 시간이 짧은 기준 정렬

시작시간이나 회의 시간이 가장 짧은 순대로 정렬을 하게 될 경우 회의가 가능한 시간대의 기회를 놓치게 되는 문제가 생겨 최적의 결과를 산출하지 못한다.

 

또한 문제에서 조건 중 회의 시작시간과 종료시간이 같은 경우가 있다.

이때는 종료시간을 기준으로 정렬하게 된다면 마지막 시간대(시작시간과 종료시간이 같은 경우)의 회의만 진행하기 때문에 최적의 결과를 산출하지 못한다. 

이를 위해 시작시간과 종료시간이 같은 경우에는 시작시간을 기준으로 정렬해야 한다.

 

코드

function solution(arr){
                let answer=0;
                arr.sort((a, b)=>{
                    if(a[1]===b[1]) return a[0]-b[0]; //회의시간과 종료시간이 같을 경우에만 시작시간으로 정렬
                    else return a[1]-b[1];
                })
                let et=0; 
                for(let x of arr){
                    if(x[0]>=et){
                        answer++;
                        et=x[1];
                    }
                }
                return answer;
            }

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