C++で実装する会議スケジューラ：2人の共通の空き時間を見つけるアルゴリズム

2人の人物それぞれの空き時間スロットのリスト slots1 と slots2、および会議の所要時間 d が与えられたとします。このとき、両者にとって都合がよく、かつ所要時間 d 以上の長さを持つ最も早い時間帯を見つける必要があります。条件を満たす共通の時間帯が存在しない場合は、空の配列を返します。

時間スロットは [start, end] という2要素の配列形式で表され、start から end までの範囲を示します。また、同じ人物の空き時間スロット同士は重ならないものと仮定できます。つまり、同じ人物の任意の2つのスロット [s1, e1] と [s2, e2] について、必ず s1 > e2 または s2 > e1 が成り立ちます。

例として、s1 = [[10,50], [60,120], [140,210]]、s2 = [[0,15], [60,70]]、duration = 8 という入力が与えられた場合、出力は [60,68] となります。

解法のアプローチ

この問題は、両者のスロットをソートした上で、2つのポインタを使って効率的に解くことができます。手順は以下の通りです。

• ポインタ i := 0、j := 0 を初期化し、結果を格納する配列 ans を用意します。さらに s1 と s2 をそれぞれソートします。
• i が s1 のサイズ未満、かつ j が s2 のサイズ未満である間、以下を繰り返します。
  • end := min(s1[i][1], s2[j][1])(重なり区間の終了時刻)
  • start := max(s1[i][0], s2[j][0])(重なり区間の開始時刻)
  • end - start >= duration であれば、ans に start と start + duration を挿入して返します。
  • そうでない場合、s1[i][1] < s2[j][1] ならば i を1増やし、そうでなければ j を1増やします。
• ループを抜けたら ans を返します(条件を満たすスロットが見つからなかった場合は空の配列)。

C++による実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
bool cmp(vector <int> a, vector <int> b){
    return a[0]<b[0];
}
class Solution {
    public:
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
        int i = 0;
        int j = 0;
        vector <int> ans;
        sort(slots1.begin(), slots1.end(), cmp);
        sort(slots2.begin(), slots2.end(), cmp);
        while(i<slots1.size() && j<slots2.size()){
            int end = min(slots1[i][1], slots2[j][1]);
            int start = max(slots1[i][0], slots2[j][0]);
            if(end-start>=duration){
                ans.push_back(start);
                ans.push_back(start+duration);
                return ans;
            } else if(slots1[i][1]<slots2[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
};
main(){
    vector<vector<int>> v = {{10,50},{60,120},{140,210}};
    vector<vector<int>> v1 = {{0,15},{60,70}};
    Solution ob;
    print_vector(ob.minAvailableDuration(v, v1, 8));
}

入力

[[10,50],[60,120],[140,210]]
[[0,15],[60,70]]
8

出力

[60, 68]

アルゴリズムのポイント

このアプローチの計算量は、ソートに O(N log N + M log M)(N、M はそれぞれのスロット数)、その後の走査に O(N + M) かかるため、全体として非常に効率的です。

重要なのは、2つのスロットの重なり部分を max(開始時刻) と min(終了時刻) で求める点です。重なりの長さが会議の所要時間以上であれば、その時点で答えが確定します。そうでなければ、終了時刻が早い方のスロットを先に進めることで、取りこぼしなく全ての候補を確認できます。