C++での最小時間差

「時：分」形式の24時間制の時点のリストがあるとすると、リスト内の任意の2つの時点間の最小分差を見つける必要があります。したがって、入力が[“ 12:30”、” 15:17”]の場合、167が返されます。

これを解決するには、次の手順に従います-

• サイズ24*60 + 1のokという配列を定義すると、最初はすべてfalseです。
• n：=tpのサイズ
• 0からn–1の範囲のiの場合
  • hr：=時間からの時間部分
  • min：=文字列の分の部分
  • 時間：=時間*60+分
  • ok [time]がtrueの場合は0を返し、それ以外の場合はok[time]をtrueに設定します。
• last：=0、first：=inf、ret：=inf、prev：=-inf
• 0〜24*60の範囲のiの場合
  • ok [i]がtrueの場合、
    • last：=max of i、last
    • 最初：=iの最小値と最初の
    • prevが–infでない場合、ret：=retの最小値およびlast– prev
    • prev：=i
• 最小のretと24*60+first-lastを返します。

理解を深めるために、次の実装を見てみましょう＆mnus;

例

#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