미용실

성공여부

걸린시간(분)

정리

완료

문제출처

제로베이스

생성 일시

Apr 16, 2025 11:47 AM

1️⃣ 문제

2️⃣ 문제 해결 전략

활동선택 문제, 회의실 배정 문제

종료 시각 기준으로 오름차순 정렬

가장 빨리 끝나는 손님(idx=0)부터 선택

선택한 손님의 끝나는 시간보다 같거나 늦게 시작하는 손님이 다음 손님(count+1) ⇒ 반복

3️⃣ 코드 및 설명

내 코드

인덱스


function solution(N, reserved) {
    var answer = 1;
    reserved.sort((a,b)=>a[0]-b[0]||a[1]-b[1])

    var [start,end] = reserved[0]
    for (let i=1;i<N;i++) {
        var [nstart,nend]=reserved[i]
        if (end<=nstart) {
            start = nstart
            end = nend
            answer++
        } else if (end-start>nend-nstart) {
            start = nstart
            end = nend
        }
    }
    return answer;
}

dfs ⇒ 시간초과


function solution(N, reserved) {
    var answer = 0;
    reserved.sort((a,b)=>a[0]-b[0]||a[1]-b[1])

    function dfs(idx,count) {
        for (let i=idx+1;i<N;i++) {
            if (idx===-1 || reserved[idx][1]<=reserved[i][0]) {
                dfs(i,count+1)
            }
        }
        answer=Math.max(answer,count)
    }

    dfs(-1,0)
    
    return answer;
}

모범 코드


function solution(N, reserved) {
    var answer = 1;
    reserved.sort((a,b)=>a[1]-b[1])

    var end = reserved[0][1]
    for (let i=1;i<N;i++) {
        var [nstart,nend]=reserved[i]
        if (end<=nstart) {
            end = nend
            answer++
        } 
    }
    return answer;
}

4️⃣ 시간복잡도

O(NlogN) ⇒ because 정렬