-
Notifications
You must be signed in to change notification settings - Fork 1
/
WeightedIntervalScheduling.java
111 lines (96 loc) · 3.26 KB
/
WeightedIntervalScheduling.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/*
* Code by:@yinengy
* Time: 11/3/2018
*
* Correspond to the algorithm state in page 256-258,
* all /* comments are from the book.
*/
import java.util.Arrays;
import java.util.Comparator;
public class WeightedIntervalScheduling {
static int[] M; // where the optimal value stored
static int[][] request; // the intervals in form {id, starting time, finishing time, weight}
static int[] p; // the last elements that is not overlapped by j
/**
* call methods to form the final algorithm
*/
public static void AlgorithmCall() {
// sort request by finishing time, O(nlogn)
Arrays.sort(request, Comparator.comparingInt(array -> array[2]));
M = new int[request.length];
p = new int[request.length];
ComputeOpt(request.length - 1); // it will change M, O(n)
System.out.print("schedule in reverse order: ");
FindSolution(request.length - 1); // get output, O(n)
}
/**
* compute value of M[j]
*
* @param j the current sub-problem's index (begin at 0 rather than 1)
*/
public static int ComputeOpt(int j) {
/* If j = 0 then */
if (j == -1) { // in fact, we have element in M[0]
/* Return 0 */
return 0;
/* Else if M[j] is not empty then */
} else if (M[j] != 0) {
/* Return M[j] */
return M[j];
/* Else */
} else {
// compute "p" which is the last elements that is not overlapped by j
p[j] = -1; // if not found, it will remain -1
for (int i = j-1; i >= 0; i--) {
if (request[i][1] <= request[j][2]) {
p[j] = i;
break;
}
}
/* Define M[j] = max(v_j+M-Compute-Opt(p(j)), M-Compute-Opt(j − 1)) */
M[j] = Math.max(request[j][3] + ComputeOpt(p[j]), ComputeOpt(j - 1));
/* Return M[j] */
return M[j];
} /* Endif */
}
/**
* main part of the algorithm
*
* @param j the current sub-problem's index (begin at 0 rather than 1)
*/
public static void FindSolution(int j) {
/* If j = 0 then */
if (j == -1) {
/* Output nothing */
} else if (j == 0) { // to avoid M out of boundary
System.out.print(request[0][0] + " ");
/* Else */
} else {
/* If v_j +M[p(j)]≥M[j − 1] then */
if (request[j][3] + M[p[j]] >= M[j - 1]) {
/* Output j together with the result of Find-Solution(p(j)) */
System.out.print(request[j][0] + " ");
FindSolution(p[j]);
/* Else */
} else {
/* Output the result of Find-Solution(j − 1) */
FindSolution(j - 1);
} /* Endif */
} /* Endif */
}
/**
* test
*/
public static void main(String[] args) {
// {id, starting time, finishing time}
request =new int[][] {{1, 0, 5, 5},
{2, 1, 3, 7},
{3, 3, 4, 8},
{4, 3, 7, 4},
{5, 4, 6, 10},
{6, 5, 8, 3},
{7, 6, 9, 1},
{8, 8, 10, 6}};
AlgorithmCall();
}
}