حل مساله تعیین توالی کارها — به زبان ساده

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} 

1# Program to find the maximum profit  
2# job sequence from a given array 
3# of jobs with deadlines and profits 
4  
5# function to schedule the jobs take 2  
6# arguments array and no of jobs to schedule 
7def printJobScheduling(arr, t): 
8  
9    # length of array 
10    n = len(arr) 
11  
12    # Sort all jobs according to  
13    # decreasing order of profit 
14    for i in range(n): 
15        for j in range(n - 1 - i): 
16            if arr[j][2] < arr[j + 1][2]: 
17                arr[j], arr[j + 1] = arr[j + 1], arr[j] 
18  
19    # To keep track of free time slots 
20    result = [False] * t 
21  
22    # To store result (Sequence of jobs) 
23    job = ['-1'] * t 
24  
25    # Iterate through all given jobs 
26    for i in range(len(arr)): 
27  
28        # Find a free slot for this job  
29        # (Note that we start from the  
30        # last possible slot) 
31        for j in range(min(t - 1, arr[i][1] - 1), -1, -1): 
32              
33            # Free slot found 
34            if result[j] is False: 
35                result[j] = True
36                job[j] = arr[i][0] 
37                break
38  
39    # print the sequence 
40    print(job) 
41  
42# Driver COde 
43arr = [['a', 2, 100], # Job Array 
44       ['b', 1, 19], 
45       ['c', 2, 27], 
46       ['d', 1, 25], 
47       ['e', 3, 15]] 
48  
49  
50print("Following is maximum profit sequence of jobs") 
51printJobScheduling(arr, 3) # Function Call 
52  
53# This code is contributed  
54# by Anubhav Raj Singh