अंतराल की एक सूची दी गई है। इस सूची में 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] के अंदर हैं।
एल्गोरिदम (सॉर्टिंग + ट्रैकिंग)
- यदि अंतराल सूची खाली है: 0 लौटाएं
- अंतराल सूची को प्रारंभ समय के आधार पर सॉर्ट करें, जब प्रारंभ समय समान हो तो अंत समय के घटते क्रम में सॉर्ट करें
end_mx := -infinityans := 0- प्रत्येक
(start, end)जोड़ी के लिए अंतराल में:- यदि
end <= end_mx:ans += 1 end_mx := max(end_mx, end)
- यदि
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