Algorithms/Java/Greedy-Algorithm/Job_Sequencing.java at main · Kumar-laxmi/Algorithms · 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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//JOB SEQUENCING IN JAVA USING GREEDY APPROACH

importjava.util.*;

classJob_Sequencing {

// Declaring variables
intn; // Size of the array/ No of jobs
Stringa[]; // String array to store job numbers
intb[]; // Integer array to store the profit associated with each job
intc[]; // Integer array to store the deadline associated with each job

// Input function to take input from user
voidinput() {
Scannersc = newScanner(System.in);
//taking user input
System.out.println("Enter number of jobs: ");
n = sc.nextInt();
a = newString[n];
b = newint[n];
c = newint[n];
System.out.println("Enter Job No, Profit and Deadline of the job");
for (inti = 0; i < n; i++) {
a[i] = sc.next();
b[i] = sc.nextInt();
c[i] = sc.nextInt();
 }
sc.close();

System.out.println("Arranged Order of Jobs: ");
System.out.print("Jobs: ");
for (inti = 0; i < n; i++) {
System.out.print(a[i] + " ");
 }
System.out.println();

System.out.print("Profit: ");
for (inti = 0; i < n; i++) {
System.out.print(b[i] + " ");
 }
System.out.println();

System.out.print("Deadline: ");
for (inti = 0; i < n; i++) {
System.out.print(c[i] + " ");
 }
System.out.println();
 }

// Arranging jobs in descending order if not sorted
voidsort() {
inttemp;
Stringtemp1;
for (inti = 0; i < n - 1; i++) {
for (intj = i + 1; j < n; j++) {
if (b[i] < b[j]) {
temp = b[i];
b[i] = b[j];
b[j] = temp;

temp = c[i];
c[i] = c[j];
c[j] = temp;

temp1 = a[i];
a[i] = a[j];
a[j] = temp1;
 }
 }
 }

//printing the arranged jobs in descending order

System.out.println();
System.out.println("Sorted Order of Jobs: ");
System.out.print("Jobs: ");
for (inti = 0; i < n; i++) {
System.out.print(a[i] + " ");
 }
System.out.println();

System.out.print("Profit: ");
for (inti = 0; i < n; i++) {
System.out.print(b[i] + " ");
 }
System.out.println();

System.out.print("Deadline: ");
for (inti = 0; i < n; i++) {
System.out.print(c[i] + " ");
 }
System.out.println();
 }

//Function to schedule the jobs and find maximum profit
voidjob_sequencing() {
intmax = c[0];
for (inti = 0; i < n; i++) {
if (c[i] > max) {
max = c[i]; // storing the maximum deadline
 }
 }

Stringa1[] = newString[max]; //Store the jobs that can yeild highest profit
//int b1[] = new int[max];
intprofit = 0;

//finding a free time slot
for (inti = 0; i < n; i++) {
intp = c[i];
p = p - 1;
if (a1[p] == null) {
a1[p] = a[i];
profit += b[i]; //If a slot is found, mark that slot with the job ID, and add its profit to the answer
 }

//else go to next job and calculate profit
else {
while (p != -1) {
if (a1[p] == null) {
a1[p] = a[i];
profit += b[i];
break;
 }
p -= 1;
 }
 }
 }

for (inti = 0; i < max; i++) {
System.out.print(" " + a1[i]);
 }
System.out.println();
System.out.print("Profit Earned " + profit); // Printing the maximised profit
 }

//driver code
publicstaticvoidmain(Stringargs[]) {
Job_Sequencingob = newJob_Sequencing();
ob.input();
ob.sort();
ob.job_sequencing();
 }
}