Sample Task and Solution : Attending Workshop in C++ of HackerRank

 A student signed up for  workshops and wants to attend the maximum number of workshops where no two workshops overlap. You must do the following:

Implement  structures:

1. struct Workshop having the following members:

   • The workshop's start time.
   • The workshop's duration.
   • The workshop's end time.

2. struct Available_Workshops having the following members:

   • An integer,  (the number of workshops the student signed up for).
   • An array of type Workshop array having size .

Implement  functions:

1. Available_Workshops* initialize (int start_time[], int duration[], int n)
   Creates an Available_Workshops object and initializes its elements using the elements in the  and  parameters (both are of size ). Here,  and  are the respective start time and duration for the  workshop. This function must return a pointer to an Available_Workshops object.

2. int CalculateMaxWorkshops(Available_Workshops* ptr)
   Returns the maximum number of workshops the student can attend—without overlap. The next workshop cannot be attended until the previous workshop ends.

Note: An array of unknown size () should be declared as follows:

DataType* arrayName = new DataType[n];

Input Format

Input from stdin is handled by the locked code in the editor; you simply need to write your functions to meet the specifications of the problem statement above.

Constraints

Output Format

Output to stdout is handled for you.

Your initialize function must return a pointer to an Available_Workshops object.
Your CalculateMaxWorkshops function must return maximum number of non-overlapping workshops the student can attend.

Sample Input

6
1 3 0 5 5 8
1 1 6 2 4 1

Sample Output

CalculateMaxWorkshops should return .

Explanation

The first line denotes , the number of workshops.
The next line contains  space-separated integers where the  integer is the  workshop's start time.
The next line contains  space-separated integers where the  integer is the  workshop's duration.

The student can attend the workshops  and  without overlap, so CalculateMaxWorkshops returns  to main (which then prints  to stdout).

Solution

#include<bits/stdc++.h>

using namespace std;

//Define the structs Workshops and Available_Workshops.

//Implement the functions initialize and CalculateMaxWorkshops

//Define the structs Workshops and Available_Workshops.

struct Workshop {

    int startTime,

        duration,

        endTime;

};

struct Available_Workshops {

    int n;

    Workshop* wss;

};

//Implement the functions initialize and CalculateMaxWorkshops

Available_Workshops* initialize (int start_time[], int duration[], int n) {

    Available_Workshops* awp = new Available_Workshops;

    awp->n = n;

    awp->wss = new Workshop[n];

    for (auto i=0; i < n; i++) {

        (awp->wss+i)->startTime = start_time[i];

        (awp->wss+i)->duration = duration[i];

        (awp->wss+i)->endTime = (awp->wss+i)->startTime + (awp->wss+i)->duration;

        //cerr << (awp->wss+i)->startTime << " " << (awp->wss+i)->duration << " " << (awp->wss+i)->endTime << "\n";

    }

    return awp;

}

int CalculateMaxWorkshops(Available_Workshops * ptr){

    multimap<int, int> mp;

    for (auto i = 0; i < ptr->n; i++)

        mp.insert(pair<int, int>( (ptr->wss+i)->endTime, (ptr->wss+i)->startTime));

   

    /*for (auto e : mp)

        cerr << e.first << " " << e.second << "\n";*/

    if (mp.size() < 2) return mp.size();

    int c = 0;

    int nextStart = -1;

    for (auto e : mp)

    {

        if (e.second >= nextStart && e.first >= nextStart)

        {

            nextStart = e.first;

            c++;

            cerr << c << ": (" << e.second << ", " << e.first << ")\n";

        }

    }

    return c;

}

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;

    cout << (ptr->wss+1)->startTime <<endl;

    return 0;

}

Source : HaclerRank