job sequence algorithm in c 2b 2b

Solutions on MaxInterview for job sequence algorithm in c 2b 2b by the best coders in the world

showing results for - "job sequence algorithm in c 2b 2b"
Johanna
16 Apr 2016
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