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

C++ में दो असंयोगी अंतरालों के न्यूनतम कुल आकार


अंतरालों की सूची दी गई है [start, end]। दो असंयोगी (non-overlapping) अंतराल चुनें जिनके आकार (end-start+1) का योग न्यूनतम हो।

अंत समय के अनुसार सॉर्ट करें। DP + बाइनरी सर्च: प्रत्येक अंतराल के लिए, उससे पहले खत्म होने वाले न्यूनतम आकार वाले अंतराल को बाइनरी सर्च द्वारा खोजें।

उदाहरण: {{2,5},{9,10},{4,6}} → [4,6] आकार 3 और [9,10] आकार 2 → कुल 5।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static bool cmp(vector& a, vector& b) { return a[1] < b[1]; }
    int solve(vector>& v) {
        int ret = INT_MAX;
        int n = v.size();
        sort(v.begin(), v.end(), cmp);
        vector dp(n);
        for (int i = 0; i < v.size(); i++) {
            int low = 0, high = i - 1;
            int temp = INT_MAX;
            int val = v[i][1] - v[i][0] + 1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (v[mid][1] >= v[i][0]) high = mid - 1;
                else { temp = min(temp, dp[mid]); low = mid + 1; }
            }
            if (temp != INT_MAX) {
                ret = min(ret, temp + val);
                dp[i] = min(val, temp);
            } else dp[i] = val;
            if (i > 0) dp[i] = min(dp[i], dp[i - 1]);
        }
        return ret == INT_MAX ? 0 : ret;
    }
};

int main() {
    Solution ob;
    vector> v = {{2,5},{9,10},{4,6}};
    cout << ob.solve(v);
    return 0;
}

इनपुट

{{2,5},{9,10},{4,6}}

आउटपुट

5
  1. - C++ में दो सूचियों का न्यूनतम इंडेक्स योग

    मान लीजिए दो दोस्त अमल और बिमल रात के खाने के लिए एक रेस्तरां चुनना चाहते हैं, अब उन दोनों के पास पसंदीदा रेस्तरां की सूची है जो स्ट्रिंग्स द्वारा दर्शाई गई है। हमें उनकी सामान्य रुचि को न्यूनतम सूची इंडेक्स योग के साथ ढूंढने में मदद करनी है। यदि विभिन्न उत्तरों के बीच चयन में टाई है, तो बिना किसी

  1. - C++ में दो सरणियों का प्रतिच्छेदन

    समस्या विवरण मान लीजिए हमारे पास दो सरणियाँ हैं; हमें उनका प्रतिच्छेदन ज्ञात करना है। उदाहरण यदि इनपुट है: [1,5,3,6,9], [2,8,9,6,7], तो आउटपुट होगा [9,6] हल करने का दृष्टिकोण इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें: दो मैप mp1, mp2 परिभाषित करें एक सरणी res परिभाषित करें nums1

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

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