मान लीजिए हमारे पास "घंटे:मिनट" प्रारूप में 24-घंटे की घड़ी के समय बिंदुओं की एक सूची है, हमें सूची में किन्हीं दो समय बिंदुओं के बीच न्यूनतम मिनट अंतर ढूंढना है। इसलिए यदि इनपुट ["12:30","15:17"] है, तो यह 167 लौटाएगा।
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
okनामक आकार24*60+1की एक सरणी परिभाषित करें, और प्रारंभ में सभी false हैं।n := tp का आकारi = 0 से n-1तक:hr := समय से घंटा भागmin := स्ट्रिंग का मिनट भागtime := hr*60 + min- यदि
ok[time]true है, तो 0 लौटाएं, अन्यथाok[time]को true सेट करें।
last := 0, first := inf, ret := inf, prev := -infi = 0 से 24*60तक:- यदि
ok[i]true है:last := max(i, last)first := min(i, first)- यदि
prev != -inf, तोret := min(ret, last-prev) prev := i
- यदि
retऔर24*60+first-lastका न्यूनतम लौटाएं।
उदाहरण
#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);
}
};
int main(){
vector<string> v = {"12:30","15:17"};
Solution ob;
cout << (ob.findMinDifference(v));
}
इनपुट
["12:30","15:17"]
आउटपुट
167