Guest User

Untitled

a guest
Jan 16th, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdlib.h>
  3. using namespace std;
  4. #define MAX(a,b) a>=b?a:b
  5. struct job
  6. {
  7. int start;
  8. int stop;
  9. int weight;
  10. };
  11.  
  12. job *jobs; int *solutions;
  13. int compare (const void * a, const void * b) { const job *ad = (job *) a; const job *bd = (job *) b; return (ad->stop - bd->stop); }
  14.  
  15.  
  16. int search(int x,int n)
  17. {
  18.  
  19.  
  20. int best=-1;
  21. for(int i=0;i<n;i++)
  22. {
  23.  
  24. if(jobs[i].stop<=jobs[x].start)
  25. {
  26. best=i;
  27. }
  28. }
  29.  
  30.  
  31. int best_stop=jobs[best].stop;
  32. int current_best=jobs[best].weight;
  33.  
  34. for(int i=0;i<n;i++)
  35. {
  36. if(jobs[i].stop==best_stop)
  37. {
  38. if(current_best<jobs[i].weight)
  39. {
  40. current_best=MAX(current_best,jobs[i].weight);
  41. best=i;
  42. }
  43. }
  44.  
  45. }
  46.  
  47. return best;
  48.  
  49.  
  50. }
  51. int sol(int i)
  52. {
  53. if(i<0)
  54. return 0;
  55. else
  56. return solutions[i];
  57.  
  58. }
  59.  
  60. int main()
  61. {
  62.  
  63.  
  64.  
  65. int t;
  66. cin>>t;
  67. while(t--)
  68. {
  69.  
  70.  
  71. int n=5;
  72. cin>>n;
  73. jobs = new job [n+1] ;
  74. solutions = new int [n+1];
  75. int p[n+1];
  76. for(int i=0;i<n;i++)
  77. { cin>>jobs[i].start;
  78. cin>>jobs[i].stop;
  79. cin>>jobs[i].weight;
  80. }
  81.  
  82. qsort(jobs, n , sizeof(job), compare);
  83.  
  84. //for(int i=0;i<n;i++)
  85. //cout<<search(i,n)<<"\n";
  86.  
  87. //array to find previous
  88. for(int i=0;i<n;i++)
  89. {
  90. p[i]=search(i,n);
  91. solutions[i]=0;
  92. }
  93.  
  94. //building solutions
  95. solutions[0]=jobs[0].weight;
  96.  
  97. for(int i=1;i<n;i++)
  98. {
  99. solutions[i]=MAX(sol(p[i])+jobs[i].weight,sol(i-1));
  100. // cout<<jobs[i].stop<<" ";
  101. // cout<<jobs[i].weight<<" ";
  102. // cout<<p[i]<<"\n";
  103. // cout<< solutions[i]<<"\n";
  104.  
  105. }
  106.  
  107.  
  108.  
  109. cout<<solutions[n-1];
  110. cout<<"\n";
  111.  
  112.  
  113.  
  114. }
  115.  
  116. return 0;
  117.  
  118. }
Add Comment
Please, Sign In to add comment