Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdlib.h>
- using namespace std;
- #define MAX(a,b) a>=b?a:b
- struct job
- {
- int start;
- int stop;
- int weight;
- };
- job *jobs; int *solutions;
- int compare (const void * a, const void * b) { const job *ad = (job *) a; const job *bd = (job *) b; return (ad->stop - bd->stop); }
- int search(int x,int n)
- {
- int best=-1;
- for(int i=0;i<n;i++)
- {
- if(jobs[i].stop<=jobs[x].start)
- {
- best=i;
- }
- }
- int best_stop=jobs[best].stop;
- int current_best=jobs[best].weight;
- for(int i=0;i<n;i++)
- {
- if(jobs[i].stop==best_stop)
- {
- if(current_best<jobs[i].weight)
- {
- current_best=MAX(current_best,jobs[i].weight);
- best=i;
- }
- }
- }
- return best;
- }
- int sol(int i)
- {
- if(i<0)
- return 0;
- else
- return solutions[i];
- }
- int main()
- {
- int t;
- cin>>t;
- while(t--)
- {
- int n=5;
- cin>>n;
- jobs = new job [n+1] ;
- solutions = new int [n+1];
- int p[n+1];
- for(int i=0;i<n;i++)
- { cin>>jobs[i].start;
- cin>>jobs[i].stop;
- cin>>jobs[i].weight;
- }
- qsort(jobs, n , sizeof(job), compare);
- //for(int i=0;i<n;i++)
- //cout<<search(i,n)<<"\n";
- //array to find previous
- for(int i=0;i<n;i++)
- {
- p[i]=search(i,n);
- solutions[i]=0;
- }
- //building solutions
- solutions[0]=jobs[0].weight;
- for(int i=1;i<n;i++)
- {
- solutions[i]=MAX(sol(p[i])+jobs[i].weight,sol(i-1));
- // cout<<jobs[i].stop<<" ";
- // cout<<jobs[i].weight<<" ";
- // cout<<p[i]<<"\n";
- // cout<< solutions[i]<<"\n";
- }
- cout<<solutions[n-1];
- cout<<"\n";
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment