Description

Submission

The optimum policy here is to accept the earliest finished workshops.

 #include<bits/stdc++.h>

using namespace std;

//Define the structs Workshops and Available_Workshops.
//Implement the functions initialize and CalculateMaxWorkshops
struct Workshop
{
    int start_time;
    int end_time;
    int duration;
};

bool operator< (const Workshop& ws1, const Workshop& ws2)
{
    return ws1.end_time < ws2.end_time;
}

struct Available_Workshops
{
    int n;
    vector<Workshop> workshops;
};

Available_Workshops* initialize (int start_time[], int duration[], int n)
{
    Available_Workshops* aw = new Available_Workshops;
    aw->n = n;
    for(int i = 0; i < n; i++) {
        Workshop ws;
        ws.start_time = start_time[i];
        ws.duration = duration[i];
        ws.end_time = ws.start_time + ws.duration;
        aw->workshops.push_back(ws);
    }
    return aw;
}

int CalculateMaxWorkshops(Available_Workshops* ptr)
{
    sort(ptr->workshops.begin(), ptr->workshops.end());
    
    int last_end = ptr->workshops.at(0).end_time;
    int count = 1;
    for(int i = 1; i < ptr->n; i++) {
        if(ptr->workshops.at(i).start_time >= last_end) {
            last_end = ptr->workshops.at(i).end_time;
            count++;
        }
    }
    return count;
}

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;
}