Given N jobs where every job is represented by following three elements of it.
1. Start Time
2. Finish Time
3. Profit or Value Associated
Find the subset of jobs associated with maximum profit such that no two jobs in the subset overlap.
Examples:
Input:
Number of Jobs n = 4
Job Details {Start Time, Finish Time, Profit}
Job 1: {1, 2, 50}
Job 2: {3, 5, 20}
Job 3: {6, 19, 100}
Job 4: {2, 100, 200}
Output:
Jobs involved in maximum profit are
Job 1: {1, 2, 50}
Job 4: {2, 100, 200}
In previous post, we have discussed about Weighted Job Scheduling problem. However, the post only covered code related to finding maximum profit. In this post, we will also print the jobs involved in maximum profit.
Let arr[0..n-1] be the input array of Jobs. We define an array DP[] such that DP[i] stores Jobs involved to achieve maximum profit of array arr[0..i]. i.e. DP[i] stores solution to subproblem arr[0..i]. The rest of algorithm remains same as discussed in previous post.
Below is its C++ implementation:
CPP
// C++ program for weighted job scheduling using Dynamic// Programming and Binary Search#include <bits/stdc++.h>using namespace std;// A job has start time, finish time and profit.struct Job{ int start, finish, profit;};// to store subset of jobsstruct weightedJob{ // vector of Jobs vector<Job> job; // find profit associated with included Jobs int value;};// A utility function that is used for sorting events// according to finish timebool jobComparator(Job s1, Job s2){ return (s1.finish < s2.finish);}// A Binary Search based function to find the latest job// (before current job) that doesn't conflict with current// job. "index" is index of the current job. This function// returns -1 if all jobs before index conflict with it. The// array jobs[] is sorted in increasing order of finish timeint latestNonConflict(Job jobs[], int index){ // Initialize 'lo' and 'hi' for Binary Search int lo = 0, hi = index - 1; // Perform binary Search iteratively while (lo <= hi) { int mid = (lo + hi) / 2; if (jobs[mid].finish <= jobs[index].start) { if (jobs[mid + 1].finish <= jobs[index].start) lo = mid + 1; else return mid; } else hi = mid - 1; } return -1;}// The main function that finds the subset of jobs// associated with maximum profit such that no two// jobs in the subset overlap.int findMaxProfit(Job arr[], int n){ // Sort jobs according to finish time sort(arr, arr + n, jobComparator); // Create an array to store solutions of subproblems. // DP[i] stores the Jobs involved and their total profit // till arr[i] (including arr[i]) weightedJob DP[n]; // initialize DP[0] to arr[0] DP[0].value = arr[0].profit; DP[0].job.push_back(arr[0]); // Fill entries in DP[] using recursive property for (int i = 1; i < n; i++) { // Find profit including the current job int inclProf = arr[i].profit; int l = latestNonConflict(arr, i); if (l != - 1) inclProf += DP[l].value; // Store maximum of including and excluding if (inclProf > DP[i - 1].value) { DP[i].value = inclProf; // including previous jobs and current job DP[i].job = DP[l].job; DP[i].job.push_back(arr[i]); } else // excluding the current job DP[i] = DP[i - 1]; } // DP[n - 1] stores the result cout << "Optimal Jobs for maximum profits are\n" ; for (int i=0; i<DP[n-1].job.size(); i++) { Job j = DP[n-1].job[i]; cout << "(" << j.start << ", " << j.finish << ", " << j.profit << ")" << endl; } cout << "\nTotal Optimal profit is " << DP[n - 1].value;}// Driver programint main(){ Job arr[] = {{3, 5, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200} }; int n = sizeof(arr)/sizeof(arr[0]); findMaxProfit(arr, n); return 0;} |
Java
// Java program for weighted job scheduling using Dynamic// Programming and Binary Searchimport java.util.*;public class WeightedJobScheduling {// A job has start time, finish time and profit.static class Job { int start, finish, profit; public Job(int start, int finish, int profit) { this.start = start; this.finish = finish; this.profit = profit; }}// to store subset of jobsstatic class weightedJob { // vector of Jobs List<Job> job; // find profit associated with included Jobs int value; public weightedJob() { job = new ArrayList<>(); }}// A utility function that is used for sorting events// according to finish timestatic class JobComparator implements Comparator<Job> { @Override public int compare(Job j1, Job j2) { return j1.finish - j2.finish; }}// A Binary Search based function to find the latest job// (before current job) that doesn't conflict with current// job. "index" is index of the current job. This function// returns -1 if all jobs before index conflict with it. The// array jobs[] is sorted in increasing order of finish timestatic int latestNonConflict(Job[] jobs, int index) { // Initialize 'lo' and 'hi' for Binary Search int lo = 0, hi = index - 1; // Perform binary Search iteratively while (lo <= hi) { int mid = (lo + hi) / 2; if (jobs[mid].finish <= jobs[index].start) { if (jobs[mid + 1].finish <= jobs[index].start) { lo = mid + 1; } else { return mid; } } else { hi = mid - 1; } } return -1;}// The main function that finds the subset of jobs// associated with maximum profit such that no two// jobs in the subset overlap.static int findMaxProfit(Job[] arr) { // Sort jobs according to finish time Arrays.sort(arr, new JobComparator());// Create an array to store solutions of subproblems. // DP[i] stores the Jobs involved and their total profit // till arr[i] (including arr[i]) weightedJob[] DP = new weightedJob[arr.length]; DP[0] = new weightedJob(); // initialize DP[0] to arr[0] DP[0].value = arr[0].profit; DP[0].job.add(arr[0]); // Fill entries in DP[] using recursive property for (int i = 1; i < arr.length; i++) { // Find profit including the current job int inclProf = arr[i].profit; int l = latestNonConflict(arr, i); if (l != -1) { inclProf += DP[l].value; } // Store maximum of including and excluding if (inclProf > DP[i - 1].value) { DP[i] = new weightedJob(); DP[i].value = inclProf; DP[i].job.addAll(DP[l].job); DP[i].job.add(arr[i]); } else { DP[i] = DP[i - 1]; } } // DP[n - 1] stores the result System.out.println("Optimal Jobs for maximum profits are"); for (Job j : DP[arr.length - 1].job) { System.out.println("(" + j.start + ", " + j.finish + ", " + j.profit + ")"); } System.out.println("\nTotal Optimal profit is " + DP[arr.length - 1].value); return DP[arr.length - 1].value;} // Driver programpublic static void main(String[] args) { Job[] arr = { new Job(3, 5, 20), new Job(1, 2, 50), new Job(6, 19, 100), new Job(2, 100, 200) }; findMaxProfit(arr);}}// This code is contributed by ratiagrawal. |
Python3
from typing import List, Tupledef find_max_profit(jobs: List[Tuple[int, int, int]]) -> int: n = len(jobs) # Sort the jobs in ascending order of their finish times jobs.sort(key=lambda x: x[1]) # Initialize DP array with the first job and its profit as the maximum profit DP = [{"value": jobs[0][2], "jobs": [jobs[0]]}] # Iterate over the remaining jobs for i in range(1, n): # Find the index of the latest non-conflicting job l = latest_non_conflict(jobs, i) # Calculate the profit that can be obtained by including the current job incl_prof = jobs[i][2] if l != -1: incl_prof += DP[l]["value"] # Update DP array with the maximum profit and set of jobs if incl_prof > DP[i - 1]["value"]: DP.append({"value": incl_prof, "jobs": DP[l]["jobs"] + [jobs[i]]}) else: DP.append(DP[i - 1]) # Print the optimal set of jobs and the maximum profit obtained print("Optimal Jobs for maximum profits are") for j in DP[-1]["jobs"]: print(f"({j[0]}, {j[1]}, {j[2]})") print(f"\nTotal Optimal profit is {DP[-1]['value']}")def latest_non_conflict(jobs: List[Tuple[int, int, int]], index: int) -> int: lo, hi = 0, index - 1 while lo <= hi: mid = (lo + hi) // 2 if jobs[mid][1] <= jobs[index][0]: if jobs[mid + 1][1] <= jobs[index][0]: lo = mid + 1 else: return mid else: hi = mid - 1 return -1# Test the program with a different set of jobsjobs = [(3, 5, 20), (1, 2, 50), (6, 19, 100), (2, 100, 200)]find_max_profit(jobs)# This code is contributed by divyansh2212 |
C#
using System;using System.Collections.Generic;public class WeightedJobScheduling { // A job has start time, finish time and profit. class Job { public int start, finish, profit; public Job(int start, int finish, int profit) { this.start = start; this.finish = finish; this.profit = profit; } } // to store subset of jobs class weightedJob { // vector of Jobs public List<Job> job; // find profit associated with included Jobs public int value; public weightedJob() { job = new List<Job>(); } } // A utility function that is used for sorting events // according to finish time class JobComparator : IComparer<Job> { public int Compare(Job j1, Job j2) { return j1.finish - j2.finish; } } // A Binary Search based function to find the latest job // (before current job) that doesn't conflict with // current job. "index" is index of the current job. // This function returns -1 if all jobs before index // conflict with it. The array jobs[] is sorted in // increasing order of finish time static int latestNonConflict(Job[] jobs, int index) { // Initialize 'lo' and 'hi' for Binary Search int lo = 0, hi = index - 1; // Perform binary Search iteratively while (lo <= hi) { int mid = (lo + hi) / 2; if (jobs[mid].finish <= jobs[index].start) { if (jobs[mid + 1].finish <= jobs[index].start) { lo = mid + 1; } else { return mid; } } else { hi = mid - 1; } } return -1; } // The main function that finds the subset of jobs // associated with maximum profit such that no two // jobs in the subset overlap. static int findMaxProfit(Job[] arr) { // Sort jobs according to finish time Array.Sort(arr, new JobComparator()); // Create an array to store solutions of // subproblems. DP[i] stores the Jobs involved and // their total profit till arr[i] (including arr[i]) weightedJob[] DP = new weightedJob[arr.Length]; DP[0] = new weightedJob(); // initialize DP[0] to arr[0] DP[0].value = arr[0].profit; DP[0].job.Add(arr[0]); // Fill entries in DP[] using recursive property for (int i = 1; i < arr.Length; i++) { // Find profit including the current job int inclProf = arr[i].profit; int l = latestNonConflict(arr, i); if (l != -1) { inclProf += DP[l].value; } // Store maximum of including and excluding if (inclProf > DP[i - 1].value) { DP[i] = new weightedJob(); DP[i].value = inclProf; DP[i].job.AddRange(DP[l].job); DP[i].job.Add(arr[i]); } else { DP[i] = DP[i - 1]; } } // DP[n - 1] stores the result Console.WriteLine( "Optimal Jobs for maximum profits are"); foreach(Job j in DP[arr.Length - 1].job) { Console.WriteLine("(" + j.start + ", " + j.finish + ", " + j.profit + ")"); } Console.WriteLine("\nTotal Optimal profit is " + DP[arr.Length - 1].value); return DP[arr.Length - 1].value; } // Driver program static void Main(string[] args) { Job[] arr = { new Job(3, 5, 20), new Job(1, 2, 50), new Job(6, 19, 100), new Job(2, 100, 200) }; findMaxProfit(arr); }}// This code is contributed by lokeshpotta20. |
Javascript
const findMaxProfit = (jobs) => { // Store the number of jobs const n = jobs.length; // Sort the jobs in ascending order of their finish times jobs.sort((a, b) => a[1] - b[1]); // Initialize DP array with the first job and its profit as the maximum profit let DP = [{ value: jobs[0][2], jobs: [jobs[0]] }]; // Iterate over the remaining jobs for (let i = 1; i < n; i++) { // Find the index of the latest non-conflicting job const l = latestNonConflict(jobs, i); // Calculate the profit that can be obtained by including the current job let inclProf = jobs[i][2]; if (l !== -1) { inclProf += DP[l].value; } // Update DP array with the maximum profit and set of jobs if (inclProf > DP[i - 1].value) { DP.push({ value: inclProf, jobs: DP[l].jobs.concat([jobs[i]]) }); } else { DP.push(DP[i - 1]); } } // Print the optimal set of jobs and the maximum profit obtained console.log("Optimal Jobs for maximum profits are"); for (const j of DP[DP.length - 1].jobs) { console.log(`(${j[0]}, ${j[1]}, ${j[2]})`); } console.log(`\nTotal Optimal profit is ${DP[DP.length - 1].value}`);};const latestNonConflict = (jobs, index) => { let lo = 0; let hi = index - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (jobs[mid][1] <= jobs[index][0]) { if (jobs[mid + 1][1] <= jobs[index][0]) { lo = mid + 1; } else { return mid; } } else { hi = mid - 1; } } return -1;};// Test the program with a different set of jobsconst jobs = [[3, 5, 20], [1, 2, 50], [6, 19, 100], [2, 100, 200]];findMaxProfit(jobs);// This code is contributed by unstoppablepandu. |
Output
Optimal Jobs for maximum profits are (1, 2, 50) (2, 100, 200) Total Optimal profit is 250
Time Complexity: O(n log n)
Auxiliary Space: O(n)
This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
