DSA/Job_sequencing_with_deadline.cpp at master · gulshan2052/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;

struct job{
	int id;
	int dead;
	int profit;
};

bool cmp(job a, job b){
	return a.profit > b.profit;
}

bool cid(job a, job b){
	return a.id < b.id;
}

int main(){
	int n;
	cin>>n;
	vector<job> v(n);
	for(int i=0;i<n;i++){
		int id,de,pr;
		cin>>id>>de>>pr;
		v[i].id = id;
		v[i].dead = de;
		v[i].profit = pr;
	}
	int deadsize = 0;
	for(int i=0;i<n;i++){
		deadsize = max(deadsize, v[i].dead);
	}
	deadsize++;
	int slot[deadsize] = {0};
	sort(v.begin(),v.end(),cmp);
	for(int i=0;i<n;i++){
		for(int j=v[i].dead;j>=1;j--){
			if(slot[j] == 0){
				slot[j] = v[i].id;
				break;
			}
		}
	}
	sort(v.begin(),v.end(),cid);
	int ct = 0;
	int pro = 0;
	for(int i=1;i<deadsize;i++){
		if(slot[i] != 0){
			ct++;
			pro += v[slot[i] - 1].profit;
		}
	}
	for(int i=0;i<deadsize;i++){
		cout<<slot[i]<<" ";
	}
	cout<<endl;
	cout<<ct<<" "<<pro;
	return 0;
}
/*
Input:
17
1 56 288
2 27 435
3 67 401
4 64 368
5 94 248
6 54 361
7 43 108
8 96 167
9 73 251
10 96 170
11 14 156
12 78 184
13 61 370
14 77 424
15 68 397
16 40 375
17 36 218

Output:
17 4921
*/