Activity Selection

Greedy টেকনিক ঃ
      সমস্যা সমাধানের জন্য আমরা সবসময়ই একটা না হয় আরেকটা এভাবে বিভিন্ন পথ খুঁজতে থাকি । এরকম প্রতিটি পথে আমরা সমস্যাটির সবচেয়ে ভালো সমাধান নিয়ে চিন্তা করি যে কিভাবে সমস্যাটি থেকে আমরা সন্তোষজনক ফলাফল বের করতে পারি । Greedy এমনই একটা টেকনিক যা বর্তমান সময়ে আমাদেরকে সবচেয়ে সন্তোষজনক ফলাফল দিয়ে থাকে । তবে এটি পরবর্তীতে সন্তোষজনক নাও হতে পারে । তাই বর্তমান সময়ে সবচেয়ে সন্তোষজনক ফলাফল পেতে আমরা Greedy টেকনিক ব্যবহার করে থাকি । এই টেকনিককে আমরা নিজেদের মত করে implement করতে পারি । সমস্যা সমাধানের ভিন্নতার কারণে আমরা কখনও simply , কখনও dynamically আবার কখনও বা recursively ; Greedy টেকনিক ব্যবহার করে থাকি ।

Activity Selection Problem :
        Problem টি হলো আমাদের কাছে কিছু Activity আছে এবং প্রতিটি Activity র start time অর্থাৎ সেই Activity কখন শুরু হয় ও finish time অর্থাৎ সেটি কখন শেষ হয় তাও দেওয়া আছে । আমাদেরকে বের করতে হবে সর্বোচ্চ কত সংখ্যক Activity select করতে পারবো যেন একটি Activity অন্য Activity কে overlap না করে । Overlap করার অর্থ হলো , যদি এমন হয় যে আমরা একটি Activity select করলাম যার start time 1 ও finish time 4 তাহলে আমরা পরবর্তীতে 1 ও 4 এই সময়ের মধ্যে শুরু হওয়া কোন Activity কে আর select করতে পারবোনা । উদাহরণস্বরূপ নিচে কিছু Activity এবং তাদের start time ও finish time দেওয়া হলো ঃ

                         

Activity number	Start Time	Finish Time
1	3	8
2	8	11
3	1	4
4	2	13
5	5	9
6	0	6
7	5	7
8	3	5
9	12	14
10	8	12
11	6	10

প্রথমে আমরা যে কাজটি করবো তা হচ্ছে end time এর ভিত্তিতে Activity গুলো sort করবো । sort করার পর sorted Activity গুলো এরকম হবে ...

তা হলে যে Activity গুলো তাড়াতাড়ি শেষ হবে ঠিক ঐ সময়ে বা তার পরে শুরু হওয়া আরেকটি Activity আমরা select করতে পারবো এবং এভাবেই maximum সংখ্যক Activity select করতে পারবো । এই পদ্ধতিতে আমরা সর্বোচ্চ 4 টি Activity select করতে পারবো । এখানেই Greedy টেকনিক ব্যবহার করা হয়েছে ।

select করা Activity number গুলো : 3,7,2,9 ।
আবার 3,7,10,9 বা 8,7,2,9 বা 8,7,10,9 এই combination এর Activity ও select করা যায় ।


Code Implementation :




Code এর output এ select করা Activity গুলো দেখাবে 3,7,2,9 । কারণ বের করার দায়িত্ব আপনাদের উপর ছেড়ে দিলাম ।

 Happy Coding

Reference :

• Introduction to Algorithms by Thomas H. Cormen