Employee Free Time

Employee Free Time

문제 내용

종업원들의 스케쥴이 주어진다

모든 스케쥴을 확인한 후 모든 종업원들이 쉬는 시간을 구하라

 

접근 방법

모든 종업원들이 쉬는 시간, 즉 업무를 진행 하지 않는 시간을 찾으면 된다.

예를 들자면

[[[1,2],[5,6]],[[1,3]],[[4,10]]] 이라는 스케쥴이 주어졌다고 생각하자

상기의 그림처럼 `3~4`를 찾는게 문제이다.

이 그림을 보면 예상이 되겠지만, 어떤 사람별 스케쥴은 의미가 없다.

즉 모든 스케쥴을 한사람의 스케쥴이라고 생각하고 쉬는 시간을 찾으면 된다.

보이는 것처럼 단 2개의 스케쥴만 확인하고 해당 스케쥴 사이의 거리를 찾으면 되는 것이다.

그럼 어떻게 스케쥴이 겹치지 않는지 확신 할 수 있는가?

이것을 이벤트로 보면 다음과 같이 정리 할 수 있다.

그럼 시작과 종료는 모두 한짝으로 되어있다.

즉 시작이 한번나오면 종료도 한번 나온다는 것이다.

이것을 숫자로 표현하자면

시작 : 1

종료 : -1

이라고 하면 3의 종료에 도착한 시점에 

시작은 2점, 종료는 -2점 이므로 모든 Sum은 0에 도달한다.

그리고 다음 시작하는 시점에 이 Sum이 0이라면

마지막 0이었던 3과

시작하는 지점 4사이에는 스케쥴이 없다고 봐도 된다.

이때 주의 할 것은 각 스케쥴은 모두 Sorting 되어있어야 한다는 것이다.

- Event의 스케쥴 시간이 빠른 순으로 정렬

- 같은 시간 순서라면 시작이 종료보다 우선 정렬

코드로 나타내면 다음과 같다.

var employeeFreeTime = function(schedule) {
    const STATUS = {START : 1, STOP : -1}
    let events = new Array();
    
    for(let i = 0; i < schedule.length; i++){
        for(let j =0; j < schedule[i].length; j++){
            let work = schedule[i][j];
            events.push([work.start,STATUS.START]);
            events.push([work.end,STATUS.STOP]);
        }
    }
    
    events.sort((a,b)=>{
        if(a[0] === b[0]){
            if(a[0] < 0){
                return -1;
            } else {
                return 1;
            }
        } else {
            return a[0] - b[0];
        }
    });
    
    let pre = -1;
    let sum = 0;
    let ans = new Array();
    
    for(let event of events){
        if(sum === 0 && 0 < pre && pre != event[0]){
            ans.push(new Interval(pre,event[0]));
        }
        pre = event[0];
        sum += event[1];
    }
    return ans;
};

Sorting을 중간에 했기때문에

O(NLogN) 이다