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

C++ में समाहित अंतराल


मान लीजिए हमारे पास अंतरालों की एक द्वि-आयामी सूची है जहां प्रत्येक अंतराल में दो मान [start, end] होते हैं। हमें जांचना है कि क्या कोई ऐसा अंतराल है जो दूसरे अंतराल को समाहित करता है।

उदाहरण के लिए, यदि इनपुट [[2,4], [5,11], [5,9], [10,10]] है, तो आउटपुट true होगा क्योंकि [5,11], [5,9] को समाहित करता है।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  • सरणी v को सॉर्ट करें
  • एक 2D सरणी ret परिभाषित करें
  • v में प्रत्येक अंतराल it के लिए:
    • यदि ret खाली है, तो it को ret के अंत में डालें
    • अन्यथा यदि ret के अंतिम तत्व का पहला मान >= it[0], तो true लौटाएं
    • अन्यथा it को ret के अंत में डालें
  • false लौटाएं

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

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

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
    }
    
    bool solve(vector<vector<int>>& v) {
        sort(v.begin(), v.end(), cmp);
        vector<vector<int>> ret;
        for (auto &it : v) {
            if (ret.empty())
                ret.push_back(it);
            else if (ret.back()[0] >= it[0])
                return true;
            else
                ret.push_back(it);
        }
        return false;
    }
};

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

इनपुट

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

आउटपुट

1
  1. C++ में जंप गेम V C++ में जंप गेम V

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी और एक पूर्णांक d है। एक चरण में हम इंडेक्स i से कूद सकते हैं: i + x जहां: i + x < n और x की सीमा 1 से d है। = 0 और x की सीमा 1 से d है। arr[k] हो। हम सरणी के किसी भी इंडेक्स से कूदना शुरू कर सकते हैं। हमें अधिकतम इंडेक्स की संख्या ज्ञात करनी है ज

  1. - C++ में इंटरवल हटाएं

    मान लीजिए हमारे पास डिस्जॉइंट इंटरवल्स की एक सॉर्टेड सूची है, प्रत्येक इंटरवल intervals[i] = [a, b] उन संख्याओं x के सेट को दर्शाता है जैसे कि a <= x < b। हमें intervals में किसी भी इंटरवल और toBeRemoved इंटरवल के बीच के इंटरसेक्शन को हटाना है। अंत में, हमें ऐसे सभी हटाने के बाद इंटरवल्स की सॉर्टेड

  1. - C++ में इंटरवल सूचियों का इंटरसेक्शन

    मान लीजिए हमारे पास क्लोज्ड इंटरवल्स की दो सूचियाँ हैं, जहाँ प्रत्येक सूची में इंटरवल्स परस्पर असंयुक्त (pairwise disjoint) हैं और सॉर्टेड क्रम में हैं। हमें इन दो इंटरवल सूचियों का इंटरसेक्शन (अंतर्व्यापन) निकालना है। हम जानते हैं कि क्लोज्ड इंटरवल [a, b] को a ≤ b के रूप में दर्शाया जाता है, जो उ