मान लीजिए हमारे पास अंतराल की एक सूची है। इस सूची में अंतराल [i] में [प्रारंभ, अंत] मान हैं। हमें यह ज्ञात करना है कि अंतरालों की संख्या दूसरे अंतराल में समाहित है। यदि कोई अंतराल है जो कई अन्य अंतरालों द्वारा समाहित है जिसे केवल एक बार गिना जाना चाहिए। एक अंतराल [s0, e0] दूसरे अंतराल [s1, e1] के अंदर होता है जब s0 s1 और e0 e1।
इसलिए, यदि इनपुट अंतराल =[[2, 6], [3, 4], [4, 7], [5, 5]] की तरह है, तो आउटपुट 2 होगा, क्योंकि [3, 4] और [ 5, 5] क्रमशः [2, 6] और [4, 7] के अंदर हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- यदि अंतराल सूची खाली है, तो
- वापसी 0
- प्रारंभ समय के आधार पर अंतराल सूची को क्रमबद्ध करें, जब प्रारंभ समय समान हों, समाप्ति समय के घटते क्रम में क्रमबद्ध करें
- end_mx :=-infinity
- उत्तर:=0
- अंतराल में प्रत्येक (प्रारंभ, अंत) जोड़ी के लिए, करें
- अगर अंत <=end_mx, तो
- उत्तर:=उत्तर + 1
- end_mx :=अधिकतम end_mx और अंत
- अगर अंत <=end_mx, तो
- वापसी उत्तर
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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, 6],[3, 4],[4, 7],[5, 5]]
आउटपुट
2