# Untitled

unknown
java
a year ago
2.1 kB
1
Indexable
Never
```package weblab;

import java.util.ArrayList;
import java.util.List;

public class Solution {

/**
* Using the memoized values from an iterative dynamic programming solution, retrieve the
* schedule with the highest total weight. NB: You may assume the jobs are sorted by ascending
* finishing time.
*
* @param n the number of jobs
* @param s the start times of the jobs for jobs 1 through n. Note that s[0] should be ignored.
* @param f the finish times of the jobs for jobs 1 through n. Note that f[0] should be ignored.
* @param v the values of the jobs for jobs 1 through n. Note that v[0] should be ignored.
* @param p the predecessors of the jobs for jobs 1 through n. Note that p[0] should be ignored
*     and that -1 represents there being no predecessor.
* @param mem where the ith element is the maximum weight of a schedule using the first i jobs.
* @return list containing the id of the jobs used in the optimal schedule, ordered by ascending
*     finishing time.
*/
public static List<Integer> solve(int n, int[] s, int[] f, int[] v, int[] p, int[] mem) {
Job[] jobs = new Job[n+1];
for(int i = 1; i <= n; i++) {
jobs[i] = new Job(s[i], f[i], v[i], p[i], mem[i], i);
}

List<Integer> results = new ArrayList<>();
int maxValue = mem[n];

int k = n;

while(k != 0) {
Job currJob = jobs[k];
int predecessor = currJob.p;

if(currJob.v + v[predecessor] == maxValue) {
k = predecessor;
} else {
k--;
}

}
return results;
}
}

class Job{

int s;
int f;
int v;
int p;
int mem;
int id;

public Job(int s, int f, int v, int p, int mem, int id) {
this.s = s;
this.f = f;
this.v = v;
this.p = p;
this.mem = mem;
this.id = id;
}
}
```