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

C++ में गैर-ओवरलैपिंग इंटरवल्स


मान लीजिए हमारे पास इंटरवल्स का एक संग्रह है। हमें न्यूनतम संख्या में इंटरवल्स हटाने हैं ताकि शेष इंटरवल्स गैर-ओवरलैपिंग (non-overlapping) हों।

उदाहरण: [[1,2],[2,3],[3,4],[1,3]] → आउटपुट 1 ([1,3] हटाएँ)।

लालची एल्गोरिदम (अंत समय द्वारा सॉर्ट)

  1. n = सरणी का आकार। यदि 0, तो 0 लौटाएँ।
  2. count = 1 (पहला इंटरवल हमेशा रखें)।
  3. सरणी को अंत समय (end) के आधार पर सॉर्ट करें।
  4. end = पहले इंटरवल का अंत।
  5. प्रत्येक इंटरवल i = 1 से n-1 के लिए:
    • यदि arr[i][0] >= end (ओवरलैप नहीं):
      • end = arr[i][1], count++।
  6. n - count लौटाएँ (हटाए जाने वाले इंटरवल्स)।

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];
    }
    
    int eraseOverlapIntervals(vector<vector<int>>& arr) {
        int n = arr.size();
        if (!n) return 0;
        int cnt = 1;
        sort(arr.begin(), arr.end(), cmp);
        int end = arr[0][1];
        for (int i = 1; i < n; i++) {
            if (arr[i][0] >= end) {
                end = arr[i][1];
                cnt++;
            }
        }
        return n - cnt;
    }
};

int main() {
    vector<vector<int>> v = {{1,2},{1,2},{1,2}};
    Solution ob;
    cout << ob.eraseOverlapIntervals(v); // 2
    return 0;
}

इनपुट

[[1,2],[1,2],[1,2]]

आउटपुट

2
  1. C++ में लाइन रिफ्लेक्शन - Y-अक्ष के समानांतर सममित रेखा जांचें C++ में लाइन रिफ्लेक्शन - Y-अक्ष के समानांतर सममित रेखा जांचें

    समस्या विवरण मान लीजिए हमारे पास 2D तल पर n बिंदु हैं, हमें जांचना है कि क्या y-अक्ष के समानांतर कोई रेखा है जो दिए गए बिंदुओं को सममित रूप से प्रतिबिंबित करती है, दूसरे शब्दों में, जांचें कि क्या कोई ऐसी रेखा मौजूद है जो सभी बिंदुओं को दी गई रेखा पर प्रतिबिंबित करने के बाद मूल बिंदुओं का समुच्चय प

  1. C++ में डायगोनल ट्रैवर्स II C++ में डायगोनल ट्रैवर्स II

    मान लीजिए हमारे पास nums नामक लिस्ट ऑफ लिस्ट है, हमें nums के सभी एलिमेंट्स को डायगोनल क्रम में दिखाना है।इसलिए, यदि इनपुट हैतो आउटपुट होगा [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:एक ऐरे ret परिभाषित करेंएक 2D ऐरे v परिभाषित करेंi := 0 से शुरू करें,

  1. - C++ में static_cast

    static_cast का उपयोग सामान्य/साधारण प्रकार रूपांतरण के लिए किया जाता है। यह निहित प्रकार जबरदस्ती (implicit type coercion) के लिए भी जिम्मेदार कास्ट है और इसे स्पष्ट रूप से भी बुलाया जा सकता है। आपको इसका उपयोग फ्लोट को इंट में, चार को इंट में आदि जैसे मामलों में करना चाहिए। यह संबंधित प्रकार के क्