#include<iostream>
#include<algorithm>
using namespace std;
struct Job
{
char id;
int dead;
int profit;
};
bool comparison(Job a, Job b)
{
return (a.profit > b.profit);
}
void printJobScheduling(Job arr[], int n)
{
sort(arr, arr+n, comparison);
int result[n];
bool slot[n];
for (int i=0; i<n; i++)
slot[i] = false;
for (int i=0; i<n; i++)
{
for (int j=min(n, arr[i].dead)-1; j>=0; j--)
{
if (slot[j]==false)
{
result[j] = i;
slot[j] = true;
break;
}
}
}
for (int i=0; i<n; i++)
if (slot[i])
cout <<endl<< arr[result[i]].id << " ";
}
int main()
{
Job arr[] = { {'a', 2, 100}, {'b', 1, 19}, {'c', 3, 27},
{'d', 1, 25}, {'e', 3, 15}};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Following is maximum profit sequence of jobs: ";
printJobScheduling(arr, n);
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+IAojaW5jbHVkZTxhbGdvcml0aG0+IAp1c2luZyBuYW1lc3BhY2Ugc3RkOyAKICAKc3RydWN0IEpvYiAKeyAKICAgY2hhciBpZDsgICAgICAKICAgaW50IGRlYWQ7ICAgIAogICBpbnQgcHJvZml0OyAgCn07IAogIApib29sIGNvbXBhcmlzb24oSm9iIGEsIEpvYiBiKSAKeyAKICAgICByZXR1cm4gKGEucHJvZml0ID4gYi5wcm9maXQpOyAKfSAKICAKdm9pZCBwcmludEpvYlNjaGVkdWxpbmcoSm9iIGFycltdLCBpbnQgbikgCnsgCiAgICBzb3J0KGFyciwgYXJyK24sIGNvbXBhcmlzb24pOyAKICAKICAgIGludCByZXN1bHRbbl07ICAKICAgIGJvb2wgc2xvdFtuXTsgICAKICAgIGZvciAoaW50IGk9MDsgaTxuOyBpKyspIAogICAgICAgIHNsb3RbaV0gPSBmYWxzZTsgCiAgCglmb3IgKGludCBpPTA7IGk8bjsgaSsrKSAKICAgIHsgCiAgICAgICBmb3IgKGludCBqPW1pbihuLCBhcnJbaV0uZGVhZCktMTsgaj49MDsgai0tKSAKICAgICAgIHsgCiAgICAgICAgICBpZiAoc2xvdFtqXT09ZmFsc2UpIAogICAgICAgICAgeyAKICAgICAgICAgICAgIHJlc3VsdFtqXSA9IGk7ICAKICAgICAgICAgICAgIHNsb3Rbal0gPSB0cnVlOyAKICAgICAgICAgICAgIGJyZWFrOyAKICAgICAgICAgIH0gCiAgICAgICB9IAogICAgfSAKICAKICAgCiAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKSAKICAgICAgIGlmIChzbG90W2ldKSAKICAgICAgICAgY291dCA8PGVuZGw8PCBhcnJbcmVzdWx0W2ldXS5pZCA8PCAiICI7IAp9IAogIAogCmludCBtYWluKCkgCnsgCiAgICBKb2IgYXJyW10gPSB7IHsnYScsIDIsIDEwMH0sIHsnYicsIDEsIDE5fSwgeydjJywgMywgMjd9LCAKICAgICAgICAgICAgICAgICAgIHsnZCcsIDEsIDI1fSwgeydlJywgMywgMTV9fTsgCiAgICBpbnQgbiA9IHNpemVvZihhcnIpL3NpemVvZihhcnJbMF0pOyAKICAgIGNvdXQgPDwgIkZvbGxvd2luZyBpcyBtYXhpbXVtIHByb2ZpdCBzZXF1ZW5jZSBvZiBqb2JzOiAiOyAKICAgIHByaW50Sm9iU2NoZWR1bGluZyhhcnIsIG4pOyAKICAgIHJldHVybiAwOyAKfQ==