2022/03/21) 8. 회의실 배정 [정렬과 그리디, 결정알고리즘]

1. 문제

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

2. 해결 방법

1. 이 문제는 끝나는 시간으로 정렬(그리디)해야한다.(회의 시간이 몇 시간인지 등 이런 것들로도 정렬할 수 있겠지만, 이게 제일 탁월한 방법이다. 그리고 끝나는 시간이 같을 경우엔 시작 시간으로 정렬해 준다.
2. 변수 et를 선언해서 0으로 초기화해준 후, x[0]이 et보다 크거나 같으면, answer++을 해준 후 et에 x[1]값을 넣어준다.

3. 정답

        <script>
            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 et=0;
                for(let x of meeting){
                    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));
        </script>

4. 후기

왜 끝나는 시간으로 정렬하는지 이해가 안갔는데, 유투브에서 귀류법으로 설명해주는 걸 보니 조금 이해가 갈 거 같긴 하다. 복습할 때 이 논리를 다시 정리하도록 하자.