//
// main.cpp
// Activity Selection
//
// Created by Himanshu on 16/08/21.
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct node Node;
struct node {
int s, f;
int pos;
};
bool cmp (const Node &a, const Node &b){
return a.f < b.f;
}
vector<int> solve(vector<int> s, vector<int> f) {
vector<int> ans;
int N = (int)s.size(), j = 0;
Node p[N];
for (int i=0; i<N; i++) {
p[i].s = s[i];
p[i].f = f[i];
p[i].pos = i;
}
sort(p, p+N, &cmp);
ans.push_back(p[0].pos);
for (int i=1; i<N; i++) {
if (p[i].s >= p[j].f) {
ans.push_back(p[i].pos);
j = i;
}
}
return ans;
}
int main() {
vector<int> start = {1, 3, 0, 5, 8, 5};
vector<int> finish = {2, 4, 6, 7, 9, 9};
vector<int> selectedActivities = solve(start, finish);
cout<<"Selected activities: \n";
for (int i=0; i<selectedActivities.size(); i++) {
cout<<selectedActivities[i]<<" ";
}
return 0;
}
Ly8KLy8gIG1haW4uY3BwCi8vICBBY3Rpdml0eSBTZWxlY3Rpb24KLy8KLy8gIENyZWF0ZWQgYnkgSGltYW5zaHUgb24gMTYvMDgvMjEuCi8vCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx2ZWN0b3I+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgc3RydWN0IG5vZGUgTm9kZTsKCnN0cnVjdCBub2RlIHsKICAgIGludCBzLCBmOwogICAgaW50IHBvczsKfTsKCmJvb2wgY21wIChjb25zdCBOb2RlICZhLCBjb25zdCBOb2RlICZiKXsKICAgIHJldHVybiBhLmYgPCBiLmY7Cn0KCnZlY3RvcjxpbnQ+IHNvbHZlKHZlY3RvcjxpbnQ+IHMsIHZlY3RvcjxpbnQ+IGYpIHsKICAgIHZlY3RvcjxpbnQ+IGFuczsKICAgIGludCBOID0gKGludClzLnNpemUoKSwgaiA9IDA7CiAgICBOb2RlIHBbTl07CiAgICAKICAgIGZvciAoaW50IGk9MDsgaTxOOyBpKyspIHsKICAgICAgICBwW2ldLnMgPSBzW2ldOwogICAgICAgIHBbaV0uZiA9IGZbaV07CiAgICAgICAgcFtpXS5wb3MgPSBpOwogICAgfQogICAgCiAgICBzb3J0KHAsIHArTiwgJmNtcCk7CiAgICBhbnMucHVzaF9iYWNrKHBbMF0ucG9zKTsKICAgIAogICAgZm9yIChpbnQgaT0xOyBpPE47IGkrKykgewogICAgICAgIGlmIChwW2ldLnMgPj0gcFtqXS5mKSB7CiAgICAgICAgICAgIGFucy5wdXNoX2JhY2socFtpXS5wb3MpOwogICAgICAgICAgICBqID0gaTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gYW5zOwp9CgppbnQgbWFpbigpIHsKICAgIHZlY3RvcjxpbnQ+IHN0YXJ0ID0gezEsIDMsIDAsIDUsIDgsIDV9OwogICAgdmVjdG9yPGludD4gZmluaXNoID0gezIsIDQsIDYsIDcsIDksIDl9OwogICAgdmVjdG9yPGludD4gc2VsZWN0ZWRBY3Rpdml0aWVzID0gc29sdmUoc3RhcnQsIGZpbmlzaCk7CiAgICAKICAgIGNvdXQ8PCJTZWxlY3RlZCBhY3Rpdml0aWVzOiBcbiI7CiAgICBmb3IgKGludCBpPTA7IGk8c2VsZWN0ZWRBY3Rpdml0aWVzLnNpemUoKTsgaSsrKSB7CiAgICAgICAgY291dDw8c2VsZWN0ZWRBY3Rpdml0aWVzW2ldPDwiICI7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=