greedy, schedule movie problem, activity selection problem

select_activities

/*
http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/
You are given n activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

1) Sort the activities according to their finishing time
2) Select the first activity from the sorted array and print it.
3) Do following for remaining activities in the sorted array.
…….a) If the start time of this activity is greater than the finish time of previously selected activity then select this activity and print it.

*/

struct movie {
    int start, end;
    movie(int s, int e) : start(s), end(e) {}
};

vector<movie> select_activities(vector<movie>& movies) {
    vector<movie> res;
    if(movies.empty()) return res;
    sort(movies.begin(), movies.end(), [](const movie& m1, const movie& m2) {return m1.end < m2.end; } );
    for(int i=0; i<movies.size(); i++) {
        if(i == 0) res.push_back(movies[i]);
        else {
            movie tail = res.back();
            if(tail.end <= movies[i].start) // <= not <
                res.push_back(movies[i]);
        }
    }
    return res;
}