[ 자바스크립트(JavaScript) ] section07 - 8 - 회의실 배정(greedy)

📍 section07 - 8 - 회의실 배정(greedy)

이번 문제는 greedy 문제다. greedy가 무엇인지 궁금하다면 이전에 작성한 글을 참고하자. 보통 정렬 문제와 자주 짝을 지어 출제되는데 강의 선생님께서 정렬 이후 순서대로 하나씩 처리하는 로직이나 우선순위 큐를 사용하는 로직은 보통 그리디로 풀면 된다고 하셨다.

 

 

문제에서 회의가 겹치지 않으면서 회의실을 사용할 수 있는 최대수의 회의를 찾으라고 했는데, 최대한 많이 회의를 하려면 끝나는 시간이 짧은 순서대로 정렬하고 풀어야 한다. 끝나는 시간이 긴 시간부터 풀게 되면 만약, 해당 시간이 끝나기 전에 2개의 회의를 진행할 수 있다면 손해기 때문이다.

 

1. 끝나는 회의 순으로 오름차순 정렬한다.
2. 이전 회의 종료시간 eT(endTime)=0으로 초기화 한다.
3. 현재 회의 시작시간과 이전 회의 종료시간을 비교하여 현재 회의 시작시간이 이전 회의 종료시간보다 크거나 같으면 회의를 진행한다. (x[0]: 현재 회의 시작시간, eT: 이전 회의 종료시간) 이후 cnt++
4. 현재 eT에는 x[1](현재 회의 종료시간)을 할당한다.
5. 반복문 끝까지 비교한다.

 

 

728x90

 

let n = 5;
let arr = [[1, 4], [2, 3], [3, 5], [4, 6], [5, 7]];

console.log(solution(n, arr));

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

    let eT = 0;
    let cnt = 0;

    for (let x of arr) {
        if (eT <= x[0]) {
            eT = x[1];
            cnt++;
        }
    }

    return cnt;
}