C++で時刻リストの最小時間差を求めるアルゴリズムと実装

24時間制の時刻を「時:分」形式の文字列で表したリストが与えられます。このリストの中から、任意の2つの時刻の組み合わせについて分単位の差を計算し、その最小値を求めるのが本記事のテーマです。例えば、入力が ["12:30", "15:17"] の場合、2つの時刻の差は167分となるため、出力は 167 になります。

ポイント：時刻は循環構造を持つ

この問題で注意すべき点は、時計の時刻が循環していることです。例えば「23:50」と「00:10」の差は、単純な引き算では1430分になりますが、実際には真夜中をまたいで20分しか離れていません。したがって、日付をまたぐケースも必ず考慮する必要があります。

解法のアプローチ

1日は1440分（24時間 × 60分）しかないため、各時刻を「0時0分からの経過分数」に変換し、サイズ1441のブール型配列に出現フラグを記録する方法が有効です。これにより、重複チェックと時刻の順次走査を高速に行えます。

手順の詳細

1. サイズ 24×60＋1 のブール型配列 ok を宣言し、すべて false で初期化します。
2. n に入力リスト tp の要素数を代入します。
3. i を 0 から n−1 まで繰り返します。
   • hr := 時刻文字列の先頭2文字（「時」の部分）を整数化した値
   • min := 4文字目以降の2文字（「分」の部分）を整数化した値
   • time := hr × 60 ＋ min
   • ok[time] がすでに true なら 0 を即座に返します（同一時刻が2つあれば差は0分のため）。そうでなければ ok[time] を true に設定します。
4. last := 0、first := INT_MAX、ret := INT_MAX、prev := INT_MIN で初期化します。
5. i を 0 から 24×60 まで順に走査し、ok[i] が true の時刻を処理します。
   • last := max(i, last)（最後に現れた時刻）
   • first := min(i, first)（最初に現れた時刻）
   • prev が INT_MIN でない場合、ret := min(ret, last − prev)（隣接する時刻同士の差の最小値を更新）
   • prev := i
6. 最後に min(ret, 24×60 ＋ first − last) を返します。24×60 ＋ first − last は「最後の時刻から最初の時刻へ真夜中をまたいだ場合の差」を表しており、これにより循環する時刻の差も正しく処理できます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int findMinDifference(vector<string>& tp) {
        vector<bool> ok(24 * 60 + 1, false);
        int n = tp.size();
        for(int i = 0; i < n; i++){
            int hr = stoi(tp[i].substr(0, 2));
            int min = stoi(tp[i].substr(3, 2));
            int time = hr * 60 + min;
            if(ok[time]) return 0;
            ok[time] = true;
        }
        int last = 0;
        int first = INT_MAX;
        int ret = INT_MAX;
        int prev = INT_MIN;
        for(int i = 0; i <= 24 * 60; i++){
            if(ok[i]){
                last = max(i, last);
                first = min(i, first);
                if(prev != INT_MIN) ret = min(ret, last - prev);
                prev = i;
            }
        }
        return min(ret, 24 * 60 + first - last);
    }
};
main(){
    vector<string> v = {"12:30","15:17"};
    Solution ob;
    cout << (ob.findMinDifference(v));
}

入力

["12:30","15:17"]

出力

167

計算量

前処理で入力リストを1回走査し（O(n)）、その後に固定長1441の配列を1回走査するだけなので（O(1440)＝定数時間）、全体の計算量は O(n) です。時刻をソートして隣接差を調べる手法（O(n log n)）と比べ、入力件数が多い場合にも安定した性能を発揮します。