You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no overlapping, in order to obtain the maximum profit.
Input: Job[] jobs = { new Job(4, 11, 25), new Job(1, 3, 50), new Job(5, 20, 90), new Job(3, 80, 185) }; Output: 235 Explanation: The optimal profit is 235, created by scheduling the jobs: 1 - 3 and 3 – 80, having profits of 50 + 185 = 235. |
Solution:
1. static class Job { 2. int start; 3. int finish; 4. int profit; 5. 6. Job(int start, int finish, int profit) { 7. this.start = start; 8. this.finish = finish; 9. this.profit = profit; 10. } 11. } 12. 13. static int latestNonConflictJob(Job[] jobs, int i) { 14. for (int j = i - 1; j >= 0; j--) { 15. if (jobs[j].finish <= jobs[i - 1].start) { 16. return j; 17. } 18. } 19. return -1; 20. } 21. 22. static int findMaxProfit(Job[] jobs) { 23. int n = jobs.length; 24. int[] profits = new int[n]; 25. profits[0] = jobs[0].profit; 26. 27. for (int i = 1; i < n; i++) { 28. int profit = jobs[i].profit; 29. int latestNonConflictJob = latestNonConflictJob(jobs, i); 30. if (latestNonConflictJob != -1) { 31. profit += profits[latestNonConflictJob]; 32. } 33. profits[i] = Math.max(profit, profits[i - 1]); 34. } 35. return profits[n - 1]; 36. } 37. 38. static int findProfit(Job[] jobs) { 39. Arrays.sort(jobs, Comparator.comparingInt(j -> j.finish)); 40. return findMaxProfit(jobs); 41. } 42.