1// Program to find the maximum profit job sequence from a given array
2// of jobs with deadlines and profits
3#include<iostream>
4#include<algorithm>
5using namespace std;
6
7// A structure to represent a job
8struct Job
9{
10 char id; // Job Id
11 int dead; // Deadline of job
12 int profit; // Profit if job is over before or on deadline
13};
14
15// This function is used for sorting all jobs according to profit
16bool comparison(Job a, Job b)
17{
18 return (a.profit > b.profit);
19}
20
21// Returns minimum number of platforms reqquired
22void printJobScheduling(Job arr[], int n)
23{
24 // Sort all jobs according to decreasing order of prfit
25 sort(arr, arr+n, comparison);
26
27 int result[n]; // To store result (Sequence of jobs)
28 bool slot[n]; // To keep track of free time slots
29
30 // Initialize all slots to be free
31 for (int i=0; i<n; i++)
32 slot[i] = false;
33
34 // Iterate through all given jobs
35 for (int i=0; i<n; i++)
36 {
37 // Find a free slot for this job (Note that we start
38 // from the last possible slot)
39 for (int j=min(n, arr[i].dead)-1; j>=0; j--)
40 {
41 // Free slot found
42 if (slot[j]==false)
43 {
44 result[j] = i; // Add this job to result
45 slot[j] = true; // Make this slot occupied
46 break;
47 }
48 }
49 }
50
51 // Print the result
52 for (int i=0; i<n; i++)
53 if (slot[i])
54 cout << arr[result[i]].id << " ";
55}
56
57// Driver program to test methods
58int main()
59{
60 Job arr[] = { {'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27},
61 {'d', 1, 25}, {'e', 3, 15}};
62 int n = sizeof(arr)/sizeof(arr[0]);
63 cout << "Following is maximum profit sequence of jobsn";
64 printJobScheduling(arr, n);
65 return 0;
66}
67