Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में न्यूनतम समय अंतर


मान लीजिए हमारे पास "घंटे:मिनट" प्रारूप में 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 := -inf
  • i = 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

  1. - C++ में दिए गए 2D सरणी में न्यूनतम योग उपमैट्रिक्स

    हमें पूर्णांक तत्वों की एक 2-D सरणी दी गई है जो मैट्रिक्स बनाती है। कार्य मैट्रिक्स से उपमैट्रिक्स निकालकर न्यूनतम योग की गणना करना है। विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं: इनपुट: int matrix[size][size] = { {2, 3, -1, 5}, {-2, 9, -1, 6}, { 5, 6, 9, -9}, { -6, 1, 1, 1} } आउटपुट: दी गई 2D सरणी म

  1. C++ में ट्री में सभी सेब इकट्ठा करने का न्यूनतम समय C++ में ट्री में सभी सेब इकट्ठा करने का न्यूनतम समय

    मान लीजिए हमारे पास n वर्टेक्स वाला एक अनडायरेक्टेड ट्री है जो 0 से n-1 तक नंबर किए गए हैं, जिनके वर्टेक्स में कुछ सेब हैं। हम ट्री के एक एज पर चलने में 1 सेकंड खर्च करते हैं। हमें वर्टेक्स 0 से शुरू करके ट्री में सभी सेब इकट्ठा करने और इस वर्टेक्स पर वापस आने में खर्च होने वाले न्यूनतम समय (सेकंड म

  1. C++ में जॉब शेड्यूल की न्यूनतम कठिनाई C++ में जॉब शेड्यूल की न्यूनतम कठिनाई

    मान लीजिए हम कार्यों की एक सूची को d दिनों में शेड्यूल करना चाहते हैं। कार्य निर्भर हैं इसलिए, i-वें कार्य पर काम करने के लिए, हमें उन सभी कार्यों j को पूरा करना होगा जहां 0 <= j < i। हमें प्रत्येक दिन कम से कम एक कार्य पूरा करना होगा। एक कार्य शेड्यूल की कठिनाई वास्तव में d दिनों में से प्रत्येक द