Going Greedy ...

This week I was doing previous challenge problems on codechef . I saw a problem which was based on greedy technique .

 Suppose you are very busy but greedy as well ;) , you have some equally valuable tasks assigned to you and you want to complete as much as you can(see here comes your greed) but tasks are not available at the start of the day you receive them after some predefined time and some tasks take longer time to complete , so what approach you should follow to complete max. no. of tasks ?

Here it is - 

1. Write down all the tasks in this manner -> end time/start time

2. Now sort them in increasing order .

3. Make a counter for no. of tasks completed and give it a value = 1 and save a variable lets say T = end[1].

3. Compare first task's end time with the start time of the next task and if ( T<=start[2] ) add 1 to the counter variable and update T  = end[2]

4. Do step 3 for all activities from 1 to N (Supposing you have a total no. of N activities).

For ex - we have these activities(start time/end time) 

1. 3 5

2. 2 6

3. 1 9

4. 7 9

5. 3 4

after writing these in end time/start time manner we have 

1. 5 3

2. 6 2

3. 9 1

4. 9 7

5. 4 3

Now after sorting them(first compare end time and if end time is equal compare start time) 

1. 4 3

2. 5 3

3. 6 2

4. 9 1

5. 9 7

Now take a variable lets say B = 1(for total no. of completed activities) and T = 4(end time of first activity)

Now look for start time which is >= T . In this example it looks like we don't have any other option other than completing first and fifth task(or third and fifth task) as time of all other activities doesn't fit properly so the answer is 2 in this case.

These kind of questions are called Maximum Activity Selection Problems. I hope you liked it.

Thanks for reading.