Sponsored
Sponsored
This approach involves processing the items and grouping them based on dependency relationships. We'll use topological sorting for individual items within a group. The main steps are:
The time complexity of this solution is O(n + m) where n is the number of items and m is the number of groups, due to the topological sort operation. The space complexity is also O(n + m) for storing the adjacency list, indegree count, and result list.
1import java.util.*;
2
3public class Solution {
4 public List<Integer> sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
5 // Assign unique groups to those without any starting group
6 int newGroupId = m;
7 for (int i = 0; i < n; i++) {
8 if (group[i] == -1) {
9 group[i] = newGroupId++;
10 }
11 }
12
13 // Initialize group and item graphs
14 List<Integer>[] itemGraph = new ArrayList[n];
15 List<Integer>[] groupGraph = new ArrayList[newGroupId];
16 int[] itemIndegree = new int[n];
17 int[] groupIndegree = new int[newGroupId];
18
19 for (int i = 0; i < n; i++) {
20 itemGraph[i] = new ArrayList<>();
21 }
22
23 for (int i = 0; i < newGroupId; i++) {
24 groupGraph[i] = new ArrayList<>();
25 }
26
27 // Build the graphs for items and groups
28 for (int i = 0; i < n; i++) {
29 for (int before : beforeItems.get(i)) {
30 itemGraph[before].add(i);
31 itemIndegree[i]++;
32 if (group[i] != group[before]) {
33 groupGraph[group[before]].add(group[i]);
34 groupIndegree[group[i]]++;
35 }
36 }
37 }
38
39 // Get sorted orders
40 List<Integer> groupOrder = topologicalSort(newGroupId, groupGraph, groupIndegree);
41 if (groupOrder.isEmpty()) return new ArrayList<>();
42
43 List<Integer> itemOrder = topologicalSort(n, itemGraph, itemIndegree);
44 if (itemOrder.isEmpty()) return new ArrayList<>();
45
46 // Sort items by group order
47 List<Integer>[] itemsWithGroupOrder = new ArrayList[newGroupId];
48 for (int i = 0; i < newGroupId; i++) {
49 itemsWithGroupOrder[i] = new ArrayList<>();
50 }
51
52 for (int item : itemOrder) {
53 itemsWithGroupOrder[group[item]].add(item);
54 }
55
56 List<Integer> result = new ArrayList<>();
57 for (int grp : groupOrder) {
58 result.addAll(itemsWithGroupOrder[grp]);
59 }
60
61 return result;
62 }
63
64 private List<Integer> topologicalSort(int n, List<Integer>[] graph, int[] indegree) {
65 Queue<Integer> zeroIndegree = new LinkedList<>();
66 List<Integer> order = new ArrayList<>();
67
68 for (int i = 0; i < n; i++) {
69 if (indegree[i] == 0) {
70 zeroIndegree.offer(i);
71 }
72 }
73
74 while (!zeroIndegree.isEmpty()) {
75 int node = zeroIndegree.poll();
76 order.add(node);
77 for (int neighbor : graph[node]) {
78 indegree[neighbor]--;
79 if (indegree[neighbor] == 0) {
80 zeroIndegree.offer(neighbor);
81 }
82 }
83 }
84
85 return order.size() == n ? order : new ArrayList<>();
86 }
87}This Java solution follows similar logic. We use ArrayLists to track dependencies, and implement topological sorting using queues for items and groups. By assigning new group IDs to items with no group, we ensure all items participate in the sorting process. The complexity and method for sorting the results are consistent with the Python solution, providing a sorted list respecting group and item constraints.
This approach incorporates priority queues (heaps) to perform topological sorting on items based on their dependencies, akin to a 'priority' based execution. It works by:
The time complexity remains O(n + m) due to the heap operations and graph traversal. Space complexity is O(n + m) to store necessary elements and dependency structures.
1#include <vector>
2#include <queue>
3#include <unordered_map>
4#include <unordered_set>
using namespace std;
vector<int> topologicalSortUsingPQ(int n, vector<vector<int>>& graph, vector<int>& indegree) {
priority_queue<int, vector<int>, greater<int>> zeroIndegree;
vector<int> order;
for (int i = 0; i < n; ++i) {
if (indegree[i] == 0) {
zeroIndegree.push(i);
}
}
while (!zeroIndegree.empty()) {
int node = zeroIndegree.top();
zeroIndegree.pop();
order.push_back(node);
for (int neighbor : graph[node]) {
if (--indegree[neighbor] == 0) {
zeroIndegree.push(neighbor);
}
}
}
return order.size() == n ? order : vector<int>();
}
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
int newGroupId = m;
for (int i = 0; i < n; ++i) {
if (group[i] == -1) {
group[i] = newGroupId++;
}
}
vector<vector<int>> itemGraph(n), groupGraph(newGroupId);
vector<int> itemIndegree(n, 0), groupIndegree(newGroupId, 0);
for (int i = 0; i < n; ++i) {
for (int before : beforeItems[i]) {
itemGraph[before].push_back(i);
++itemIndegree[i];
if (group[i] != group[before]) {
groupGraph[group[before]].push_back(group[i]);
++groupIndegree[group[i]];
}
}
}
vector<int> groupOrder = topologicalSortUsingPQ(newGroupId, groupGraph, groupIndegree);
if (groupOrder.empty()) return {};
vector<int> itemOrder = topologicalSortUsingPQ(n, itemGraph, itemIndegree);
if (itemOrder.empty()) return {};
unordered_map<int, vector<int>> itemsGrouped;
for (int item : itemOrder) {
itemsGrouped[group[item]].push_back(item);
}
vector<int> result;
for (int grp : groupOrder) {
result.insert(result.end(), itemsGrouped[grp].begin(), itemsGrouped[grp].end());
}
return result;
}The C++ solution utilizes a min-priority queue for managing items with zero dependencies. This ensures items are processed in order of their natural indices, which mimics the behavior of prioritizing certain operations. After identifying initial independent items, it iterates through the graph, managing dependencies and constructing the correct order through traditional topological sorting mechanisms. The heap structure adds an extra layer of determinism by processing the lowest index 'ready' item first.