DP #14. Weighted Job Scheduling. - mbhushan/dynpro GitHub Wiki
(14). Weighted Job Scheduling.
Given certain jobs with start and end time and amount you make on finishing the job, find the maximum value you can make by scheduling jobs in non-overlapping way.
Formula:
Jobs [] = {(1,3), (2,5), (4,6), (6,7), (5,8), (7,9)};
Weights = {5, 6, 5, 4, 11, 2};
for (int i=0; i<jobs.len; i++) {
for (int j=i+1; j<jobs.len; j++) {
if (!overlap(jobs[i], jobs[j]) {
values[i] = Max (value[j], value[i] + weights[j]);
parent[j] = i;
}
}
}
I0 = Iteration 0
I1 = Iteration 1
etc..
| Index -> |
0 |
1 |
2 |
3 |
4 |
5 |
| Jobs -> |
(1, 3) |
(2, 5) |
(4, 6) |
(6, 7) |
(5, 8) |
(7, 9) |
| weights -> |
5 |
6 |
5 |
4 |
11 |
2 |
| Iterations 0 |
5 |
6 |
10 |
9 |
16 |
7 |
| I1 |
5 |
6 |
10 |
10 |
17 |
8 |
| I2 |
5 |
6 |
10 |
14 |
17 |
12 |
| I3 |
5 |
6 |
10 |
14 |
17 |
16 |
| I4 |
5 |
6 |
10 |
14 |
17 |
16 |
|
|
|
|
|
|
|
| Parents |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
| I0 |
-1 |
-1 |
0 |
0 |
0 |
0 |
| I1 |
-1 |
-1 |
0 |
1 |
1 |
1 |
| I2 |
-1 |
-1 |
0 |
2 |
1 |
2 |
| I4 |
-1 |
-1 |
0 |
2 |
1 |
3 |
Weighted Job Scheduling
- Time Complexity: O(n^2)
- Space Complexity: O(n)