Hackerrank Attending Workshops Solution
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:
struct Workshop having the following members:
- The workshop's start time.
- The workshop's duration.
- The workshop's end time.
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:
- 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. - 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 in cpp
Approach 1.
struct Workshop
{
int start;
int duration;
int end;
};
struct Available_Workshops
{
int N;
vector<Workshop> v;
Available_Workshops(int &n)
{
v = vector<Workshop>(n);
N = n;
}
};
bool compare(Workshop &w1, Workshop &w2)
{
return w1.end < w2.end;
}
Available_Workshops *initialize(int start_time[], int duration[], int n)
{
Available_Workshops *AW = new Available_Workshops(n);
for(int i=0;i<n;i++)
{
AW->v[i].start = start_time[i];
AW->v[i].duration = duration[i];
AW->v[i].end = start_time[i] + duration[i];
}
sort(AW->v.begin(),AW->v.end(),compare);
return AW;
}
int CalculateMaxWorkshops(Available_Workshops* ptr)
{
int end_time=0;
int count=0;
for(int i=0;i<ptr->N; i++)
if(ptr->v[i].start >= end_time)
{
end_time = ptr->v[i].end;
count += 1;
}
return count;
}
Approach 2.
//Define the structs Workshops and Available_Workshops.
//Implement the functions initialize and CalculateMaxWorkshops
struct Workshop
{
int start_time;
int duration;
int end_time;
};
struct Available_Workshops
{
int n;//signed up
Workshop *arr = new Workshop[n];
};
Available_Workshops* initialize (int start_time[], int duration[], int n)
{
Available_Workshops *aw = new Available_Workshops[n];
aw->n=n;
for (int i=0;i<n;i++)
{
aw->arr[i].start_time = start_time[i];
aw->arr[i].duration = duration[i];
aw->arr[i].end_time = start_time[i]+duration[i];
}
return aw;
}
int CalculateMaxWorkshops(Available_Workshops* ptr)
{
sort(ptr->arr,(ptr->arr)+ptr->n,[](Workshop &a,Workshop &b){return a.end_time < b.end_time;});
int curEnd = 0;
int res = 0;
for(auto i = ptr->arr;i != (ptr->arr)+ptr->n;++i){
if(i->start_time >= curEnd){
res++;
curEnd = i->end_time;
}
}
return res;
}
Approach 3.
//Define the structs Workshops and Available_Workshops.
//Implement the functions initialize and CalculateMaxWorkshops
struct Workshop{
int start_time;
int duration;
int end_time;
};
struct Available_Workshops{
int n;
Workshop* buf;
Available_Workshops(int n):n(n),buf(new Workshop[n]){
}
};
Available_Workshops* initialize (int start_time[], int duration[], int n) {
Available_Workshops* res = new Available_Workshops(n);
for(int i = 0;i < n;++i){
((res->buf)+i)->start_time = start_time[i];
((res->buf)+i)->duration = duration[i];
((res->buf)+i)->end_time = start_time[i] + duration[i];
}
return res;
}
int CalculateMaxWorkshops(Available_Workshops* ptr) {
sort(ptr->buf,(ptr->buf)+ptr->n,[](Workshop &a,Workshop &b){return a.end_time < b.end_time;});
int curEnd = 0;
int res = 0;
for(auto i = ptr->buf;i != (ptr->buf)+ptr->n;++i){
if(i->start_time >= curEnd){
res++;
curEnd = i->end_time;
}
}
return res;
}