Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- //Define the structs Workshops and Available_Workshops.
- //Implement the functions initialize and CalculateMaxWorkshops
- struct Workshops{
- int start_time,duration,end_time;
- };
- struct Available_Workshops{
- int n;
- Workshops* ptr;
- };
- Available_Workshops* initialize (int start_time[], int duration[], int n){
- Available_Workshops* aw=new Available_Workshops[1];
- aw->ptr=new Workshops[n]{};
- aw->n=n;
- for(int i=0;i<n;i++){
- aw->ptr[i].start_time=start_time[i];
- aw->ptr[i].duration=duration[i];
- aw->ptr[i].end_time=start_time[i]+duration[i];
- }
- return aw;
- }
- bool overlap(const Workshops& a, const Workshops& b){
- if(b.start_time>=a.start_time && b.start_time<a.end_time){
- return true;
- }
- else if(a.start_time>=b.start_time && a.start_time<b.end_time){
- return true;
- }
- return 0;
- }
- int cmp(const void* a, const void* b){
- Workshops* aa=(Workshops*)a;
- Workshops* bb=(Workshops*)b;
- if(overlap(*aa, *bb)){
- return aa->end_time-bb->end_time;
- }
- return aa->start_time-bb->start_time;
- }
- int CalculateMaxWorkshops(Available_Workshops* ptr){
- qsort(ptr->ptr,ptr->n,sizeof(Workshops),cmp);
- // int s=0;
- int e=0;
- int c=0;
- for(int i=0;i<ptr->n;i++){
- if(!i){
- e=ptr->ptr[i].end_time;
- c++;
- }
- else if(ptr->ptr[i].start_time>=e){
- e=ptr->ptr[i].end_time;
- c++;
- }
- }
- return c;
- }
- //locked below this point
- int main(int argc, char *argv[]) {
- int n; // number of workshops
- cin >> n;
- // create arrays of unknown size n
- int* start_time = new int[n];
- int* duration = new int[n];
- for(int i=0; i < n; i++){
- cin >> start_time[i];
- }
- for(int i = 0; i < n; i++){
- cin >> duration[i];
- }
- Available_Workshops * ptr;
- ptr = initialize(start_time,duration, n);
- cout << CalculateMaxWorkshops(ptr) << endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment