Attending Workshops in C++ – Solution in Hacker Rank - hackerranksolutions8

 

Problem

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

Implement 2 structures:
1. struct Workshop having the following members:
        1. The workshop’s start time.
        2. The workshop’s duration.
        3. The workshop’s end time.
2. struct Available_Workshops having the following members:
        1. An integer, n (the number of workshops the student signed up for).
        2. An array of type Workshop array having size n.

Implement 2functions:

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 start_timr[] and duration[] parameters (both are of size n). Here, start_time[i] and duration[i] are the respective start time and duration for the ith 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 (n) should be declared as follows

---

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 :

• 1<= N <= 10^5
• 0 <= start_timei <= 10^3
• 0 <= durationi <= 10^3

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 4.

Explanation :

The first line denotes n, the number of workshops.
The next line contains n space-separated integers where the ith integer is the ith workshop’s start time
The student can attend the workshops 0,1,3 and 5 without overlap, so CalculateMaxWorkshops returns 4 to main (which then prints 4 to stdout).

---

Solution :

//Attending Workshops in C++ - Hacker Rank Solution
#include<bits/stdc++.h>

using namespace std;

//Define the structs Workshops and Available_Workshops.
//Implement the functions initialize and CalculateMaxWorkshops
/* Attending Workshops in C++ - Hacker Rank Solution START */
#include <vector>
#include <iostream>

typedef pair<int,int> p;
typedef vector<p> Available_Workshops;

Available_Workshops* initialize(int *start_time, int *duration, int n) {
    auto aw = new Available_Workshops(n);
    for(int i = 0; i < n; i++){
        aw->at(i).first = start_time[i];
        aw->at(i).second = start_time[i]+duration[i];
    }
    return aw;
}

int CalculateMaxWorkshops(Available_Workshops* data) {
    sort(data->begin(),data->end(), [](const p &a, const p &b) { return a.second < b.second; });
    int f = 0, res = 0;
    for(int i = 0; i < data->size(); i++){
        if(data->at(i).first >= f){
            res++;
            f = data->at(i).second;
        }
    }
    return res;
}
/* Attending Workshops in C++ - Hacker Rank Solution END */

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