#include <bits/stdc++.h>
using namespace std;
// A job has a start time, finish time and profit.
struct Activitiy
{
int start, finish;
};
// A utility function that is used for sorting
// activities according to finish time
bool activityCompare(Activitiy s1, Activitiy s2)
{
return (s1.finish < s2.finish);
}
// Returns count of the maximum set of activities that can
// be done by a single person, one at a time.
void printMaxActivities(Activitiy arr[], int n)
{
// Sort jobs according to finish time
sort(arr, arr+n, activityCompare);
cout << "Following activities are selected n";
// The first activity always gets selected
int i = 0;
cout << "(" << arr[i].start << ", " << arr[i].finish << "), ";
// Consider rest of the activities
for (int j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (arr[j].start >= arr[i].finish)
{
cout << "(" << arr[j].start << ", "
<< arr[j].finish << "), ";
i = j;
}
}
}
// Driver program
int main()
{
Activitiy arr[] = {{1, 1}, {1, 2}, {1, 3}, {1, 4},
{1, 5}, {1, 6},{1,7}};
int n = sizeof(arr)/sizeof(arr[0]);
printMaxActivities(arr, n);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKLy8gQSBqb2IgaGFzIGEgc3RhcnQgdGltZSwgZmluaXNoIHRpbWUgYW5kIHByb2ZpdC4Kc3RydWN0IEFjdGl2aXRpeQp7CiAgICBpbnQgc3RhcnQsIGZpbmlzaDsKfTsKIAovLyBBIHV0aWxpdHkgZnVuY3Rpb24gdGhhdCBpcyB1c2VkIGZvciBzb3J0aW5nCi8vIGFjdGl2aXRpZXMgYWNjb3JkaW5nIHRvIGZpbmlzaCB0aW1lCmJvb2wgYWN0aXZpdHlDb21wYXJlKEFjdGl2aXRpeSBzMSwgQWN0aXZpdGl5IHMyKQp7CiAgICByZXR1cm4gKHMxLmZpbmlzaCA8IHMyLmZpbmlzaCk7Cn0KIAovLyBSZXR1cm5zIGNvdW50IG9mIHRoZSBtYXhpbXVtIHNldCBvZiBhY3Rpdml0aWVzIHRoYXQgY2FuCi8vIGJlIGRvbmUgYnkgYSBzaW5nbGUgcGVyc29uLCBvbmUgYXQgYSB0aW1lLgp2b2lkIHByaW50TWF4QWN0aXZpdGllcyhBY3Rpdml0aXkgYXJyW10sIGludCBuKQp7CiAgICAvLyBTb3J0IGpvYnMgYWNjb3JkaW5nIHRvIGZpbmlzaCB0aW1lCiAgICBzb3J0KGFyciwgYXJyK24sIGFjdGl2aXR5Q29tcGFyZSk7CiAKICAgIGNvdXQgPDwgIkZvbGxvd2luZyBhY3Rpdml0aWVzIGFyZSBzZWxlY3RlZCBuIjsKIAogICAgLy8gVGhlIGZpcnN0IGFjdGl2aXR5IGFsd2F5cyBnZXRzIHNlbGVjdGVkCiAgICBpbnQgaSA9IDA7CiAgICBjb3V0IDw8ICIoIiA8PCBhcnJbaV0uc3RhcnQgPDwgIiwgIiA8PCBhcnJbaV0uZmluaXNoIDw8ICIpLCAiOwogCiAgICAvLyBDb25zaWRlciByZXN0IG9mIHRoZSBhY3Rpdml0aWVzCiAgICBmb3IgKGludCBqID0gMTsgaiA8IG47IGorKykKICAgIHsKICAgICAgLy8gSWYgdGhpcyBhY3Rpdml0eSBoYXMgc3RhcnQgdGltZSBncmVhdGVyIHRoYW4gb3IKICAgICAgLy8gZXF1YWwgdG8gdGhlIGZpbmlzaCB0aW1lIG9mIHByZXZpb3VzbHkgc2VsZWN0ZWQKICAgICAgLy8gYWN0aXZpdHksIHRoZW4gc2VsZWN0IGl0CiAgICAgIGlmIChhcnJbal0uc3RhcnQgPj0gYXJyW2ldLmZpbmlzaCkKICAgICAgewogICAgICAgICAgY291dCA8PCAiKCIgPDwgYXJyW2pdLnN0YXJ0IDw8ICIsICIKICAgICAgICAgICAgICA8PCBhcnJbal0uZmluaXNoIDw8ICIpLCAiOwogICAgICAgICAgaSA9IGo7CiAgICAgIH0KICAgIH0KfQogCi8vIERyaXZlciBwcm9ncmFtCmludCBtYWluKCkKewogICAgQWN0aXZpdGl5IGFycltdID0ge3sxLCAxfSwgezEsIDJ9LCB7MSwgM30sIHsxLCA0fSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgezEsIDV9LCB7MSwgNn0sezEsN319OwogICAgaW50IG4gPSBzaXplb2YoYXJyKS9zaXplb2YoYXJyWzBdKTsKICAgIHByaW50TWF4QWN0aXZpdGllcyhhcnIsIG4pOwogICAgcmV0dXJuIDA7Cn0=