সমস্যার বিবরণ: এই প্রব্লেমে আমাদের n সংখ্যক event দেওয়া থাকবে। প্রতিটি even একটি নির্দিষ্ট সময়ে শুরু হবে এবং একটি নির্দিষ্ট সময়ে শেষ হবে। শুরু এবং শেষ দুটি সময়ই [1,30000] এই ব্যবধির integer হবে। আর n এর মানের ব্যবধি হল [1,100000].
আমরা event time overlap করে এমন কোন দুটি event এর যেকোনো একটিতে যোগদান করতে পারব। আমরা তাহলে maximum কয়টি event এ যোগদান করতে পারব সেটি বের করতে হবে।
সমাধান: এটি একটি Basic Dynamic Programming problem. এখানে observation টি হচ্ছে সময় integer এবং এর maximum value 30000 হতে পারে।
আমরা dp নামে একটি array রাখবো, যেখানে dp[ i ] এর value নির্দেশ করবে i-তম মিনিট বা তার আগে শেষ হয়ে যাওয়া event গুলোর মধ্যে maximum কয়টি event এ যোগদান করতে পারব সেটি। তাহলে আমরা dp[ 30000 ] এর value কে main answer হিসেবে print করতে পারব, তাই না?
এখন আসা যাক আমরা এই dp array কে কিভাবে calculate করব। আমরা প্রথমে event গুলোকে তাদের শুরু হওয়ার সময় ধরে ascending order এ sort করে নিবো।
এবার আমরা 1 থেকে 30000 মিনিটের উপর loop চালাবো। ধরি, এখন আমরা loop এর ভিতর j-তম মিনিটে আছি। এখন আমরা dp[ j ] এর value কে max(dp[ j ], dp[ j - 1 ]) দিয়ে update করব। কারণ dp[ j ] এর value j তম মিনিট বা তার আগে শেষ হয়ে যাওয়া সকল answer এর মধ্যে maximum কে নির্দেশ করে।
এখন একেবারে মূল কাজটি বাকি। আমরা যখন j-তম মিনিটে আছি, তখন যদি আমরা দেখি যে i-তম event টি j-তম মিনিটে শুরু হচ্ছে, তবে আমরা ওই event এর end time এর জন্য dp[endtimei] এর value কে update করব max(dp[ j-1 ] + 1, dp[endtimei] ) দিয়ে। কারণ ( j-1 ) - তম মিনিটের পর আমরা শুধু i-তম event অর্থাৎ শুধু একটি event এ যোগদান করতে পারব যেটি endtimei পর্যন্ত চলবে, অথবা already যদি dp[endtimei] এর মান dp[j-1]+1 থেকে বড় হয়ে থাকে, তবে আমরা সেটিকেই consider করব।
এভাবে আমাদের main answer টি dp[30000] এর মধ্যে calculated হয়ে store হয়ে যাবে। আসলে যে event টি সবার শেষে শেষ হবে, ওই শেষ মিনিট পর্যন্ত calculate করলেই আমাদের main answer হয়ে যায়।
My Solution Code:
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন