-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathProcess Schedule optiver
115 lines (98 loc) · 3.06 KB
/
Process Schedule optiver
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
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Main {
static class ProcessSchedule {
public ProcessSchedule(int startTime, int endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
public int startTime;
public int endTime;
}
static class Dependency {
public Dependency(int pid1, int pid2) {
this.pid1 = pid1;
this.pid2 = pid2;
}
public int pid1;
public int pid2;
}
static class Scheduler {
ArrayList<int[]> p = new ArrayList<>();
ArrayList<ArrayList<Integer>> d = new ArrayList<>();
int n;
public Scheduler(Vector<ProcessSchedule> processes, Vector<Dependency> dependencies) {
p = new ArrayList<>();
d = new ArrayList<>();
n = processes.size();
for(int i = 0; i < n; i++) {
p.add(new int[]{processes.get(i).startTime, processes.get(i).endTime});
}
for(int i = 0; i < n; i++) {
d.add(new ArrayList<>());
}
for(int i = 0; i < dependencies.size(); i++) {
int u = dependencies.get(i).pid1 - 1;
int v = dependencies.get(i).pid2 - 1;
d.get(u).add(v);
}
}
boolean cycle() {
int indegree[] = new int[n];
for(int i = 0; i < n;i++) {
for(int j: d.get(i)) {
indegree[j]++;
}
}
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
if (indegree[i] == 0)
q.add(i);
}
int cnt = 0;
Vector<Integer> topOrder = new Vector<Integer>();
while (!q.isEmpty()) {
int u = q.poll();
topOrder.add(u);
for (int node : d.get(u)) {
if (--indegree[node] == 0)
q.add(node);
}
cnt++;
}
// Check if there was a cycle
if (cnt != n) {
return false;
}
return true;
}
public void PrintSchedule() {
if(cycle()) {
System.out.println("IMPOSSIBLE");
return;
}
boolean[] vis = new boolean[n];
for(int i = 0; i < n; i++) {
if(!vis[i]) {
dfs(i, vis);
}
}
for(int[] i: p) {
System.out.println(i[0] +" " +i[1]);
}
}
public void dfs(int i, boolean[] vis) {
if(vis[i]) return;
vis[i] = true;
for(int j: d.get(i)) {
p.get(j)[0] = Math.max(p.get(i)[0] + 1, p.get(j)[0]);
p.get(j)[1] = Math.min(p.get(i)[1] - 1, p.get(j)[2]);
dfs(j, vis);
}
}
}
}