मान लीजिए हमारे पास अंतरालों की एक सूची है जहां प्रत्येक अंतराल [start, end) जैसा है और हमारे पास types नामक स्ट्रिंग्स की एक सूची भी है। अब दिए गए i के लिए, intervals[i] types[i] कार्य पर काम करने के समय को [start, end) से दर्शाता है। एक ही प्रकार के दो अंतराल कभी ओवरलैप या स्पर्श नहीं करते। इसलिए हमें एक सॉर्ट की गई मर्ज की गई सूची ढूंढनी है जहां प्रत्येक आइटम में [start, end, num_types] हो, जो दर्शाता है कि start से end तक, num_types संख्या में कार्य किए जा रहे थे।
इसलिए, यदि इनपुट intervals = [[0, 3], [5, 7], [0, 7]] types = ["problem solving", "news","game play"] जैसा है, तो आउटपुट [[0, 3, 2], [3, 5, 1],[5, 7, 2]] होगा, क्योंकि हमारे पास ये कार्य हो रहे हैं: [0, 3) के बीच "problem solving" और "game play", [3, 5) के बीच "game play", और [5, 7) के बीच "news" और "game play"।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
ev := एक नई सूची
प्रत्येक अंतराल start end जोड़ी (s, e) के लिए intervals में, करें
(s, 1) को ev के अंत में जोड़ें
(e, -1) को ev के अंत में जोड़ें
सूची ev को सॉर्ट करें
cnt := 0, last := -1
ans := एक नई सूची
प्रत्येक समय और इंक्रीमेंट पैरामीटर (t, inc) के लिए ev में घटनाओं के, करें
यदि t, last के समान नहीं है और cnt, 0 के समान नहीं है, तो
cnt := cnt + inc
last := t
ans वापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
class Solution: def solve(self, intervals, jobs): ev = [] for s, e in intervals: ev.append((s, 1)) ev.append((e, -1)) ev.sort() cnt = 0 last = -1 ans = [] for t, inc in ev: if t != last and cnt != 0: ans.append([last, t, cnt]) cnt += inc last = t return ans ob = Solution() intervals = [ [0, 3], [5, 7], [0, 7] ] types = ["problem solving", "news", "game play"] print(ob.solve(intervals, types))
इनपुट
[[0, 3],[5, 7],[0, 7]], ["problem solving", "news", "game play"]
आउटपुट
[[0, 3, 2], [3, 5, 1], [5, 7, 2]]