[Javascript] 프로그래머스 - 호텔 대실

문제 설명

호텔에서는 최소한의 객실을 사용하여 예약 손님을 받으려고 합니다. 퇴실 후에는 10분간 청소 시간이 필요하며, 그 이후에 다음 손님이 입실할 수 있습니다.
예약 시간이 문자열 형태로 주어진 2차원 배열 book_time이 주어질 때, 필요한 최소 객실의 개수를 구하는 함수를 작성해야 합니다.

제한 사항

• 1 ≤ book_time의 길이 ≤ 1,000
• book_time[i]는 ["HH:MM", "HH:MM"] 형태의 배열이며, [대실 시작 시각, 대실 종료 시각]을 나타냅니다.
• 시각은 24시간 표기법을 따르며 "00:00"부터 "23:59"까지 주어집니다.
• 예약 시각이 자정을 넘어가는 경우는 없습니다.
• 시작 시각은 항상 종료 시각보다 빠릅니다.

해결 방법

알고리즘: 스위핑(Sweep Line) 알고리즘

1. 시각을 분 단위로 변환하는 함수 getTime(time)을 정의합니다.
2. 모든 예약의 시작 시각과 종료 후 10분이 지난 시각을 타임라인에 기록합니다.
   • 입실 시 +1, 퇴실(청소 포함) 시 -1을 기록합니다.
3. 타임라인을 시간 순으로 정렬하되, 시간이 같다면 퇴실(-1)이 먼저 오도록 정렬합니다.
4. 타임라인을 순회하면서 현재 사용 중인 객실 수를 갱신하고, 최대값을 구합니다.

시간 복잡도

• 타임라인에 2n개의 이벤트가 저장되므로 O(n)의 공간이 필요합니다.
• 정렬 연산은 O(n log n), 이후 순회하며 계산하는 과정은 O(n)이므로 최종 시간 복잡도는 O(n log n)입니다.

시간 복잡도

function getTime(time) {
    return parseInt(time.slice(0, 2)) * 60 + parseInt(time.slice(3));
}

function solution(book_time) {
    let answer = 0;
    let timeline = [];
    
    for (const [start, end] of book_time) {
        const startTime = getTime(start);
        const endTime = getTime(end) + 10;

        timeline.push([startTime, 1]);
        timeline.push([endTime, -1]);
    }

    timeline.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

    let current = 0;
    for (const [_, delta] of timeline) {
        current += delta;
        answer = Math.max(answer, current);
    }

    return answer;
}