-
Notifications
You must be signed in to change notification settings - Fork 1
/
SortItemsByGroupsRespectingDependencies.java
125 lines (104 loc) · 3.97 KB
/
SortItemsByGroupsRespectingDependencies.java
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
class Solution {
private List<Integer>[] groupItems; // Stores items belonging to each group.
private List<Integer>[] itemGraph; // Stores the graph of item dependencies.
private int[] itemIndegrees; // Stores the indegree of each item.
private int[] groupIndegrees; //// Stores the indegree of each group.
public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
buildGroupItems(n, group);
buildItemGraph(n, beforeItems, group);
int[] result = new int[n];
int index = 0;
Queue<Integer> groupQueue = new LinkedList<>();
// Initialize the queue with groups that have no incoming dependencies.
for (int i = 0; i < n; i++) {
if (groupIndegrees[i] == 0) {
groupQueue.offer(i);
}
}
// Topological sort on groups
while (!groupQueue.isEmpty()) {
Integer groupId = groupQueue.poll();
List<Integer> itemsInGroup = groupItems[groupId];
if (itemsInGroup != null) {
Queue<Integer> itemQueue = new LinkedList<>();
// Initialize the queue with items that have no incoming dependencies within the group.
for (var item : itemsInGroup) {
if (itemIndegrees[item] == 0) {
itemQueue.offer(item);
}
}
while (!itemQueue.isEmpty()) {
Integer item = itemQueue.poll();
result[index++] = item;
if (itemGraph[item] != null) {
for (var neighbor : itemGraph[item]) {
itemIndegrees[neighbor]--;
if (group[neighbor] != groupId) {
if (--groupIndegrees[group[neighbor]] == 0) {
groupQueue.offer(group[neighbor]);
}
} else if (itemIndegrees[neighbor] == 0) {
itemQueue.offer(neighbor);
}
}
}
}
}
}
// If all items have been placed in the result array, return the result; otherwise, return an empty array.
return index == n ? result : new int[0];
}
/**
0 -1
1 -1
2 1
3 0
4 0
5 1
6 0
7 -1
-----------
WHERE ITS -1 MOVE IT TO END OF ARRAY INDEX AS NEW GROUP NUMBER
0 7
1 6
2 1
3 0
4 0
5 1
6 0
7 5
------
*/
private void buildGroupItems(int n, int[] group) {
groupItems = new List[n];
int index = n - 1;
// Organize items into groups and store them in the groupItems array.
for (int i = 0; i < n; i++) {
if (group[i] == -1) {
group[i] = index--;
}
if (groupItems[group[i]] == null) {
groupItems[group[i]] = new ArrayList<>();
}
groupItems[group[i]].add(i);
}
}
private void buildItemGraph(int n, List<List<Integer>> beforeItems, int[] group) {
itemGraph = new List[n];
itemIndegrees = new int[n];
groupIndegrees = new int[n];
// Build the item dependency graph and calculate indegrees for both items and groups.
for (int i = 0; i < n; i++) {
for (int j : beforeItems.get(i)) {
if (itemGraph[j] == null) {
itemGraph[j] = new ArrayList<>();
}
itemGraph[j].add(i);
itemIndegrees[i]++;
if (group[i] != group[j]) {
groupIndegrees[group[i]]++;
}
}
}
}
}