package project005; import java.util.*; class Job{ int start; int finish; int profit; public Job(int s, int e, int val){ start = s; finish = e; profit = val; } } // Time Complexity: O(n^2) class Project005{ public static int[] jobIndexes; public static int k; public int latestNonConflictingJob(Job[] jobs, int n){ for(int i = n - 1; i >= 0; i--){ if(jobs[i].finish <= jobs[n].start) return i; } return -1; } // Memoization public int maxProfitRecur(Job[] jobs, int n, int[] dp){ if(n < 0) return 0; if(dp[n] != -1) return dp[n]; // include nth job or not int profitIncludingCur = jobs[n].profit; int nextJob = latestNonConflictingJob(jobs, n); if(nextJob != -1) profitIncludingCur += maxProfitRecur(jobs, nextJob, dp); int profitExcludingProfit = maxProfitRecur(jobs, n-1, dp); dp[n] = Math.max(profitIncludingCur, profitExcludingProfit); return dp[n]; } public int maxProfitMemoization(Job[] jobs){ int n = jobs.length; // Sort by finish time Arrays.sort(jobs, new Comparator(){ @Override public int compare(Job a, Job b){ return Integer.compare(a.finish, b.finish); } }); int[] dp = new int[n]; Arrays.fill(dp, -1); return maxProfitRecur(jobs, n - 1, dp); } // Table public int maxProfit(Job[] jobs){ int n = jobs.length; // Sort by finish time Arrays.sort(jobs, new Comparator(){ @Override public int compare(Job a, Job b){ return Integer.compare(a.finish, b.finish); } }); int[] dp = new int[n]; dp[0] = jobs[0].profit; for(int i = 1; i < n; i++){ dp[i] = Math.max(jobs[i].profit, dp[i - 1]); // Find non-conflicting job before for(int j = i - 1; j >= 0; j--){ if(jobs[j].finish <= jobs[i].start){ dp[i] = Math.max(jobs[i].profit + dp[j], dp[i - 1]); } } } return dp[n - 1]; } public static void main(String[] args){ int jobArray[][] = {{3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}}; int n = jobArray.length; Job[] t = new Job[n]; for(int i = 0; i < n; i++){ for(int j = 0; j < 1; j++) t[i] = new Job(jobArray[i][j], jobArray[i][j + 1], jobArray[i][j + 2]); } Project005 s = new Project005(); System.out.println("The maximum profit is: " + s.maxProfit(t)); for(int i = 0; i < jobIndexes.length; i++) System.out.println("The jobs used were: " + jobIndexes[i]); } }

Set up a method to display the indexes of the jobs used. Above is the code that I have so far.