activity scheduling.md

Activity Scheduling (Dynamic approach)

The table we are going to build for this activity scheduling problem will track the number of activities we can schedule, given a list of activities sorted by finish time. We will try to maximize the number of activities we can schedule. Consider a following activities that we need to choose from.

We want to solve it using the dynamic approach so we create a table of (n+1) X (n+1) to store our data for the dynamic programming. Each item say c[i][j] means number of activities that can be scheduled in between activity[i] and activity[j].

Following table is the final table we get, if we use the dynamic programming to solve the above problem.

#	0	1	2	3	4	5	6	7	8	9	10	11
1	0	0	0	0	1	0	1	1	2	2	0	3
2	0	0	0	0	0	0	0	0	1	1	0	2
3	0	0	0	0	0	0	0	0	1	1	0	2
4	0	0	0	0	0	0	0	0	0	0	0	1
5	0	0	0	0	0	0	0	0	0	0	0	1
6	0	0	0	0	0	0	0	0	0	0	0	0
7	0	0	0	0	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0	0	0	0	0
9	0	0	0	0	0	0	0	0	0	0	0	0
10	0	0	0	0	0	0	0	0	0	0	0	0
11	0	0	0	0	0	0	0	0	0	0	0	0
12	0	0	0	0	0	0	0	0	0	0	0	0

How to read this table.

The table says that

c[i][j] = the total number of activities that can occur in between activity[i], activity[j]

Consider the first row for c[1]

#	0	1	2	3	4	5	6	7	8	9	10	11
1	0	0	0	0	1	0	1	1	2	2	0	3

Say c[1][3]=0 means that if I select 1 as my first execution activity then I select 3 after that, how many activities have been selected for execution. Its 0 since activity 3 doesn't qualify (start time of activity 3 is less than finish time of activity 1) and there is no activity in between finish of 1 and start of 3

Now say c[1][4]=1 means that if I begin with activity 1 and I now select activity 4, how many activities do we have ? Its 1 since 4 can be executed after activity 1. and similar case with c[1][6] and c[1][7].

Now for c[1][8]=2 activity 8 can be executed after activity 4 so we can use the c[1][4] and increment the value. Its just like you can execute activity 8 after activity 4 which is executed after activity 1. so the cost sums up.

You can iterate it this way and create the whole table. Also important thing to notice is that the activities are sorted ascending order by their finish time so values below the diagonal are always zero. And it makes sense if we consider an example like c[6][4]. This basically says that we want to execute 6 first and then go to 4. that is not possible since the we have sorted activity by the time 6 finishes 4 would already have been finished. So we can safely begin populating table above the diagonal part.

Hope this doesn't confuse you more.