মান ল করুন intervals নামের একটি ইন্টারভালের তালিকা যেখানে প্রতিটি ইন্টারভাল [start, end) ফর্মে এবং types নামের একটি স্ট্রিংয়ের তালিকা। 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 := একটি নতুন তালিকা।
প্রতিটি (s, e) ইন্টারভালের জন্য:
(s, 1) ev-এ যোগ করুন।
(e, -1) ev-এ যোগ করুন।
ev তালিকাটি সাজান।
cnt := 0, last := -1
ans := একটি নতুন তালিকা।
ev-এ থাকা প্রতিটি (t, inc) জন্য:
যদি t != last এবং cnt != 0 হয়, তবে ans-এ [last, t, cnt] যোগ করুন।
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]]
