[인프런 섹션7] 회의실 배정 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션7] 회의실 배정 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-27

1. 회의 겹치지 않게, 최대 수의 회의

2. 그리디?

• 현재 단계에서 가장 최선의 선택을 하는 알고리즘

3. 회의실 사용시간이 짧은 순으로 정렬

4. for 반복문

• 첫번째 회의 종료시점 = end
• 초기값 cnt = 1
• 회의 시작시점이 end보다 크거나 같은 경우 cnt++, end는 해당 회의의 종료시점

let cnt = 1;
let end = arr[0][1];

for (let i=1; i<arr.length; i++) {
    if (arr[i][0] >= end) {
        cnt++;
        end = arr[i][1];
    }
}

문제점
시작하자마자 종료하는 회의가 있는 경우
기대결과와 실행결과가 다름

5. 해결방법

• 희의 종료시간이 가장 빠른 순으로 정렬
• 회의 종료시간이 같은 경우, 회의 시작시간 순으로 정렬

회의 시작시간을 오름차순으로 정렬하는 이유
[3, 3], [1, 3] 내림차순으로 정렬하면 두번째 회의를 배정할 수 없다.

sort((a, b) => a[1] !== b[1] ? a[1]-b[1] : a[0]-b[0]);

✍️소스코드

2021-06-27

function solution(arr) {
    arr.sort((a, b) => a[1] !== b[1] ? a[1] - b[1] : a[0] - b[0]);
    let cnt = 1;

    let end = arr[0][1];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i][0] >= end) {
            cnt++;
            end = arr[i][1];
        }
    }

    return cnt;
}