HackerRank, c++, Attending Workshops

greedy algorithm 문제,

이걸 모든 경우의 수를 계산해서 접근하는 방식으로 생각했으나,

말이 안되는 거라 생각했더니 greedy algorithm 이더라,

 

즉 workshop이 시작하는 시간으로 정렬(예외가 있음)

workshop이 진행되는 시간이 가장 낮은 것으로 정렬(예외가 있음)

workshop이 마무리 되는 시간으로 정렬..

 

#include<bits/stdc++.h>

using namespace std;
#include <vector>


//Define the structs Workshops and Available_Workshops.
//Implement the functions initialize and CalculateMaxWorkshops
struct Workshops{
    int startTime;
    int endTime;    
    int duration;
};

struct Available_Workshops{
    int n;
    vector<Workshops*> ary;
};

Available_Workshops* initialize(int *start_time, int* duration, int n)
{
    Available_Workshops *availableWorkshop = (Available_Workshops*)malloc(sizeof(Available_Workshops));
    
    for( int i = 0 ; i < n; i++)
    {
        Workshops *workshop = (Workshops*)malloc(sizeof(Workshops));
        workshop->startTime = start_time[i];
        workshop->duration = duration[i];
        workshop->endTime = start_time[i] + duration[i];
        availableWorkshop->ary.push_back(workshop);
    }
    return availableWorkshop;
}



int CalculateMaxWorkshops(Available_Workshops *ptr)
{
    int max = 0;
    
    sort(ptr->ary.begin(), ptr->ary.end(), [](const Workshops *a, const Workshops*b){
        return a->endTime < b->endTime;
    });
    
    int endTime = 0;
    for( unsigned int i = 0 ; i < ptr->ary.size(); i++)
    {
        if(endTime <= ptr->ary[i]->startTime)
        {
            max++;
            endTime = ptr->ary[i]->endTime;
        }
    }
        
    return max;
}
int main(int argc, char *argv[]) {