C++로 풀어보는 직원 공통 자유 시간(Employee Free Time) 문제

문제 설명

여러 명의 직원 근무 일정(schedule) 목록이 주어졌다고 가정해 보겠습니다. 이 목록은 각 직원의 근무 시간을 나타내며, 각 직원은 서로 겹치지 않는 구간(interval)들의 리스트를 가지고 있고, 이 구간들은 이미 정렬되어 있다고 가정합니다. 우리가 구해야 하는 것은 모든 직원에게 공통으로 해당하면서 길이가 양수인 자유 시간(free time) 구간의 목록이며, 결과 역시 정렬된 순서로 반환해야 합니다.

구간은 [x, y] 형태로 표현합니다. 예를 들어 schedule[0][0].start = 1, schedule[0][0].end = 2라면 이는 [1, 2] 구간을 의미합니다.

입력이 다음과 같다고 해보겠습니다.

schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]]

첫 번째 직원은 [1, 2]와 [5, 6]에, 두 번째 직원은 [1, 3]에, 세 번째 직원은 [4, 10]에 근무합니다. 이때 세 사람 모두 근무하지 않는 공통 자유 시간은 [3, 4] 하나뿐이므로 출력은 다음과 같습니다.

[[3,4]]

접근 방식

핵심 아이디어는 간단합니다. 모든 직원의 구간을 한곳에 모아 시작 시간을 기준으로 정렬하면, 인접한 구간 사이의 빈틈(gap)이 곧 모든 직원의 공통 자유 시간이 됩니다. 단계별로 정리하면 다음과 같습니다.

구간 통합: 모든 직원의 구간을 하나의 2차원 배열 v에 담습니다.
정렬: 시작 시간을 기준으로 v를 오름차순 정렬합니다.
빈틈 탐색: 결과 배열 ret을 준비하고 temp에 첫 번째 구간을 저장한 뒤, v를 순회하며 다음을 반복합니다.
- 현재 구간의 시작 시간이 temp의 종료 시간보다 크면(두 구간 사이에 빈틈이 존재하면) {temp의 종료, 현재 구간의 시작}을 ret에 추가하고 temp를 현재 구간으로 갱신합니다.
- 그렇지 않다면 두 구간이 겹치는 것이므로, 종료 시간이 더 늦은 구간으로 temp를 갱신합니다.
반환: 순회가 끝나면 ret을 반환합니다.

C++ 구현

위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << "[";
        for(int j = 0; j < v[i].size(); j++){
            cout << v[i][j];
            if(j + 1 < v[i].size()) cout << ", ";
        }
        cout << "]";
        if(i + 1 < v.size()) cout << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b){
        return a[0] < b[0];
    }

    vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>> schedule) {
        // 1. 모든 직원의 구간을 하나의 배열로 모은다
        vector<vector<int>> v;
        for (int i = 0; i < schedule.size(); i++) {
            for (int j = 0; j < schedule[i].size(); j++) {
                v.push_back(schedule[i][j]);
            }
        }

        // 2. 시작 시간 기준으로 정렬한다
        sort(v.begin(), v.end(), cmp);

        // 3. 인접한 구간 사이의 빈틈을 찾는다
        vector<vector<int>> ret;
        vector<int> temp = v[0];
        for (int i = 1; i < v.size(); i++) {
            if (temp[1] < v[i][0]) {              // 빈틈 발견 → 공통 자유 시간
                ret.push_back({temp[1], v[i][0]});
                temp = v[i];
            } else {                              // 구간이 겹침 → 병합
                temp = temp[1] < v[i][1] ? v[i] : temp;
            }
        }
        return ret;
    }
};

int main(){
    Solution ob;
    vector<vector<vector<int>>> v = {{{1,2},{5,6}},{{1,3}},{{4,10}}};
    print_vector(ob.employeeFreeTime(v));
}

구현 시 주의점: 순회는 반드시 두 번째 구간(i = 1)부터 시작해야 하며, 빈틈 판정 조건은 temp[1] < v[i][0](이전 구간의 종료가 현재 구간의 시작보다 앞서는 경우)이어야 합니다. 첫 구간부터 비교하거나 비교 대상을 잘못 지정하면 엉뚱한 구간이 결과에 포함되므로 주의하세요.

실행 결과

입력:

{{{1,2},{5,6}},{{1,3}},{{4,10}}}

출력:

[[3, 4]]

복잡도 분석

전체 구간의 개수를 N이라고 하면, 정렬 단계에서 O(N log N), 이후 선형 순회에서 O(N)이 소요되므로 전체 시간 복잡도는 O(N log N)입니다. 모든 구간을 별도의 배열에 저장하므로 공간 복잡도는 O(N)입니다.