C++で従業員の共通の空き時間を求めるアルゴリズムを解説

従業員の勤務スケジュールのリストが与えられているとします。このリストは各従業員の勤務時間を表しています。各従業員は互いに重ならない区間（インターバル）のリストを持ち、それらはすでにソート済みです。ここでの課題は、すべての従業員に共通する「正の長さを持つ空き時間（フリータイム）」を表す有限区間のリストを求め、その結果もソートされた順序で返すことです。

区間は [x, y] の形式で表現します。たとえば schedule[0][0].start = 1、schedule[0][0].end = 2 のように指定します。

入力が schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] の場合、出力は [[3,4]] となります。これは、従業員1が 1〜2 と 5〜6 に勤務し、従業員2が 1〜3、従業員3が 4〜10 に勤務しているため、全員が同時に空いている時間帯は 3〜4 だけだからです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• すべての従業員の区間を1つの2次元配列 v にまとめます（フラット化）。

• 配列 v を開始時刻の昇順でソートします。

• 結果を格納する2次元配列 ret を用意します。

• 一時変数 temp を v[0] で初期化します。

• v の各要素に対して次の処理を行います。

  • temp の終了時刻が現在の区間の開始時刻より前の場合（＝隙間がある場合）、その隙間 {temp[1], v[i][0]} を ret に追加し、temp を現在の区間で更新します。

  • そうでない場合（＝区間が重なっている場合）、終了時刻がより大きい方の区間で temp を更新します。

• 最後に ret を返します。

この手法のポイントは、全区間を開始時刻順に並べることで、「直前の区間の終了時刻」と「次の区間の開始時刻」の間に隙間があれば、それは必ず全従業員に共通する空き時間になるという点です。

実装例

理解を深めるために、以下のC++の実装を見てみましょう。

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

void print_vector(vector<vector<auto>> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << "[";
        for(int j = 0; j < v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        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) {
        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]);
            }
        }
        sort(v.begin(), v.end(), cmp);
        vector<vector<int>> ret;
        vector<int> temp = v[0];
        for (int i = 0; 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;
    }
};

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

入力

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

出力

[[3, 4]]

計算量

N を全区間の総数とすると、ソートに O(N log N)、その後のマージ処理に O(N) かかるため、全体の時間計算量は O(N log N) です。空間計算量は、区間を格納するために O(N) となります。