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

Python प्रोग्राम - अन्य अंतराल के अंदर पूरी तरह से समाहित अंतराल की संख्या गिनें

अंतराल की एक सूची दी गई है। इस सूची में interval[i] में [start, end] मान हैं। हमें उन अंतराल की संख्या खोजनी है जो किसी अन्य अंतराल द्वारा समाहित हैं। यदि कोई अंतराल कई अन्य अंतराल द्वारा समाहित है तो उसे केवल एक बार गिना जाना चाहिए। एक अंतराल [s0, e0] दूसरे अंतराल [s1, e1] के अंदर है जब s0 >= s1 and e0 <= e1।

उदाहरण

इनपुट: intervals = [[2, 6], [3, 4], [4, 7], [5, 5]]

आउटपुट: 2

व्याख्या: [3, 4] और [5, 5] क्रमशः [2, 6] और [4, 7] के अंदर हैं।

एल्गोरिदम (सॉर्टिंग + ट्रैकिंग)

  1. यदि अंतराल सूची खाली है: 0 लौटाएं
  2. अंतराल सूची को प्रारंभ समय के आधार पर सॉर्ट करें, जब प्रारंभ समय समान हो तो अंत समय के घटते क्रम में सॉर्ट करें
  3. end_mx := -infinity
  4. ans := 0
  5. प्रत्येक (start, end) जोड़ी के लिए अंतराल में:
    • यदि end <= end_mx: ans += 1
    • end_mx := max(end_mx, end)
  6. ans लौटाएं

Python कार्यान्वयन

def solve(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: (x[0], -x[1]))
    end_mx = float("-inf")
    ans = 0
    for start, end in intervals:
        if end <= end_mx:
            ans += 1
        end_mx = max(end_mx, end)
    return ans

intervals = [[2, 6], [3, 4], [4, 7], [5, 5]]
print(solve(intervals))  # आउटपुट: 2

इनपुट/आउटपुट

Input: [[2, 6], [3, 4], [4, 7], [5, 5]]
Output: 2
  1. - Python प्रोग्राम - अन्य अंतराल के अंदर पूरी तरह से समाहित अंतराल की संख्या गिनें

    अंतराल की एक सूची दी गई है। इस सूची में interval[i] में [start, end] मान हैं। हमें उन अंतराल की संख्या खोजनी है जो किसी अन्य अंतराल द्वारा समाहित हैं। यदि कोई अंतराल कई अन्य अंतराल द्वारा समाहित है तो उसे केवल एक बार गिना जाना चाहिए। एक अंतराल [s0, e0] दूसरे अंतराल [s1, e1] के अंदर है जब = s1 and e0

  1. पायथन में ऐरे में x से बड़े सभी वैल्यूज को फ़िल्टर करने का प्रोग्राम पायथन में ऐरे में x से बड़े सभी वैल्यूज को फ़िल्टर करने का प्रोग्राम

    मान लीजिए हमारे पास nums नामक संख्याओं की सूची है। हमारे पास x नामक एक और संख्या भी है। हमें nums से उन सभी नंबरों को फ़िल्टर करके ढूंढना है जो x से कम हैं। पायथन में filter() मेथड होता है जो फंक्शन को आर्गुमेंट के रूप में लेता है और इस फंक्शन का उपयोग करके फ़िल्टर करता है। तो, यदि इनपुट nums = [1,5

  1. पायथन में दिए गए एज को शामिल करने वाले अद्वितीय पथों की संख्या गिनने का प्रोग्राम पायथन में दिए गए एज को शामिल करने वाले अद्वितीय पथों की संख्या गिनने का प्रोग्राम

    मान लीजिए हमारे पास (u, v) के रूप में एज की सूची है जो एक ट्री दर्शाती है। प्रत्येक एज के लिए हमें उन अद्वितीय पथों की कुल संख्या ज्ञात करनी है जिनमें वह एज शामिल है, उसी क्रम में जैसे इनपुट में दिया गया है। उदाहरण के लिए, यदि इनपुट है edges = [[0, 1],[0, 2],[1, 3],[1, 4]], तो आउटपुट [6, 4, 4, 4] ह