Untitled

mail@pastecode.io avatar
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) {
              results.add(predecessor);
              results.add(currJob.id);
              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;
    }
}