Given a list of tasks, each composed of a start and an end time, return the maximum set of tasks which are compatible. Two tasks are compatible if they don't overlap.struct comparator
{
bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right)
{
return left.second < right.second;
}
};
vector<pair<int, int>> IntervalScheduling(vector<pair<int, int>> &tasks)
{
if (tasks.size() < 1)
return tasks;
vector<pair<int, int>> ret;
// Sort by the end times
sort(tasks.begin(), tasks.end(), comparator());
// Iterate and select the immediate compatible start in a greedy manner
ret.push_back(tasks[0]);
for (int i = 1; i < tasks.size(); i++)
if (ret[ret.size() - 1].second <= tasks[i].first)
ret.push_back(tasks[i]);
return ret;
} |