C++의 최소 시차

<시간/>

"시:분" 형식의 24시간제 시간 포인트 목록이 있다고 가정하면 목록에 있는 두 시간 포인트 간의 최소 분 차이를 찾아야 합니다. 따라서 입력이 ["12:30","15:17"]과 같으면 167이 반환됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

24*60 + 1 크기의 ok라는 배열을 정의하고 처음에는 모두 거짓입니다.
n :=tp의 크기
0 ~ n – 1 범위의 i에 대해
- hr :=시간에서 시간 부분
- min :=문자열의 분 부분
- 시간:=시간 * 60 + 분
- ok[time]이 true이면 0을 반환하고, 그렇지 않으면 ok[time]을 true로 설정합니다.
마지막 :=0, 첫 번째 :=inf, ret :=inf, 이전 :=-inf
0 ~ 24*60 범위의 i용
- ok[i]가 참이면
  - last :=i의 최대값, 마지막
  - first :=i의 최소값과 첫 번째
  - prev가 –inf가 아니면 ret :=ret의 min이고 마지막 – prev
  - 이전 :=나
ret 및 24*60+처음부터 마지막까지의 최소값을 반환합니다.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. &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"]

C++의 최소 시차

예시

입력

출력