Advertisement
kartikkukreja

Scheduling to minimize lateness

Nov 24th, 2013
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. class Job {
  6. public:
  7.     int deadline, length;
  8.  
  9.     bool operator < (const Job& x) const   {
  10.         return deadline < x.deadline;
  11.     }
  12. } *jobs;
  13.  
  14. int main()  {
  15.     int N, i, last_finished, s, lateness, temp;
  16.  
  17.     scanf("%d", &N); // Number of jobs
  18.     jobs = new Job[N];
  19.     for (i = 0; i < N; i++) // deadline and length of each job
  20.         scanf("%d %d", &jobs[i].deadline, &jobs[i].length);
  21.     scanf("%d", &s); // time at which the jobs become available
  22.  
  23.     // sort jobs in non-decreasing order of deadline
  24.     sort(jobs, jobs + N);
  25.  
  26.     // print the optimal solution
  27.     printf("Optimal schedule :\n");
  28.     for (i = 0, last_finished = s, lateness = 0; i < N; i++)    {
  29.         // job i runs from last_finished to last_finished + jobs[i].length
  30.         temp = last_finished + jobs[i].length;
  31.         printf("Job %d : [%d, %d]\n", i, last_finished, temp);
  32.         last_finished = temp;
  33.        
  34.         // If last_finished > jobs[i].deadline
  35.     // then lateness of job i = last_finished - jobs[i].deadline
  36.     // otherwise lateness of job i = 0
  37.     temp = max(last_finished - jobs[i].deadline, 0);
  38.     if (lateness < temp)
  39.         lateness = temp;
  40.     }
  41.     printf("Maximum lateness of schedule : %d\n", lateness);
  42.  
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement