ধরুন আমাদের অনুরোধ করা_ট্রিপস নামে একটি ম্যাট্রিক্স আছে যেখানে প্রতিটি সারি রয়েছে [start_x, end_x, num_passengers], এবং আমাদের একটি ক্ষমতার মানও রয়েছে। এখন প্রতিটি অনুরোধ করা ট্রিপে start_x-এ num_passengers যাত্রী নিতে এবং end_x-এ তাদের নামতে বলে। আমাদের কাছে প্রদত্ত ক্ষমতা সহ একটি গাড়িও রয়েছে এবং x =0 অবস্থানে শুরু হয়। আমরা প্রত্যেক যাত্রীকে তুলতে চাই এবং শুধুমাত্র ডান দিকে যেতে পারি, আমাদের পরীক্ষা করতে হবে যে আমরা সবাইকে পিক আপ এবং ড্রপ করতে পারি কিনা।
সুতরাং, যদি ইনপুটটি ট্রিপের মত হয় =[[1, 25, 2], [3, 4, 3], [5, 12, 3]] ক্ষমতা =6, তাহলে আউটপুট হবে True
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ঘটনা :=একটি নতুন তালিকা
-
ট্রিপে প্রতিটি সেটের (sx, ex, np) জন্য, করুন
-
ইভেন্টের শেষে জোড়া (sx, np) সন্নিবেশ করুন
-
ইভেন্টের শেষে জোড়া (ex, −np) সন্নিবেশ করুন
-
-
বহন :=0
-
প্রতিটি জোড়ার জন্য (loc, delta) ইভেন্টের তালিকায় (বাছাই ক্রমে), করুন
-
বহন :=বহন + ডেল্টা
-
যদি বহন করা হয়>ক্ষমতা, তাহলে
-
রিটার্ন ফলস
-
-
-
রিটার্ন ট্রু
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution: def solve(self, trips, capacity): events = [] for sx, ex, np in trips: events.append((sx, np)) events.append((ex, -np)) carrying = 0 for loc, delta in sorted(events): carrying += delta if carrying > capacity: return False return True ob = Solution() trips = [ [1, 25, 2], [3, 4, 3], [5, 12, 3] ] capacity = 6 print(ob.solve(trips, capacity))
ইনপুট
trips = [ [1, 25, 2], [3, 4, 3], [5, 12, 3] ] capacity = 6
আউটপুট
True