not sure why this example is solved using dfs not khan’s algorithm
Yeah, very strange for solution to not solve with khan’s algorithm bfs here
it looks like it’s updated with khan’s algo
Expected output is “ok” which is incorrect.
In C#, when I ran my code, the Expected Output is showing “ok”. Please check.
Expected output is “ok” which is incorrect. Please, fix it.
What do you mean?
Expected Output reads “OK” which is incorrect for C#. Please fix.
Thank you for pointing out. We will fix it.
Still not fixed. Should be the output itself.
from typing import List
from collections import deque
def task_scheduling(tasks: List[str], requirements: List[List[str]]) → List[str]:
# WRITE YOUR BRILLIANT CODE HERE
#
# 1- Construct the graph
# 2- build the count of parent that will contain all parents in the graph
# 3- build the topology sort processing:
# a- Initialize the queue that expected to contain each node
# from the count of parent above.
# b- Using queue to sort the child of each node of the graph,
# put result in a list and return it
def count_parent(graph):
# Use of HashMap for parent counting from the graph
counts = {node:0 for node in graph}
for parent in graph:
for node in graph[parent]:
counts[node] += 1
return counts
def topo_sort(graph):
result = []
q = deque()
counts = count_parent(graph)
for node in counts:
if counts[node] == 0:
q.append(node)
while len(q) > 0:
node = q.popleft()
result.append(node)
for child in graph[node]:
counts[child] -= 1
if counts[child] == 0:
q.append(child)
return result if len(result) == len(graph) else None
graph = {t: [] for t in tasks}
for a,b in requirements:
graph[a].append(b)
return topo_sort(graph)
I am not sure if this is correct solution, but it passes all the cases
def task_scheduling(tasks: List[str], requirements: List[List[str]]) → List[str]:
graph = defaultdict(list)
for pre, task in requirements:
graph[task].append(pre)
visited = set()
def dfs(task):
if task in visited:
return
visited.add(task)
for nei in graph[task]:
dfs(nei)
result.append(task)
result = []
for task in tasks:
dfs(task)
return result
public static List<String> taskScheduling(List<String> tasks, List<List<String>> requirements) {
Map<String, List<String>> graph = new HashMap<>();
for (String task : tasks) {
graph.put(task, new ArrayList<>());
}
for (List<String> requirement : requirements) {
graph.get(requirement.get(0)).add(requirement.get(1));
}
return topoSort(graph);
}
private static Map<String, Integer> countParents(Map<String, List<String>> graph) {
Map<String, Integer> hm = new HashMap<>();
for (String key : graph.keySet()) {
hm.put(key, 0);
}
for (Map.Entry<String, List<String>> entry : graph.entrySet()) {
for(String node : entry.getValue()) {
hm.put(node, hm.get(node) + 1);
}
}
return hm;
}
private static List<String> topoSort(Map<String, List<String>> graph) {
List<String> result = new ArrayList<>();
ArrayDeque<String> queue = new ArrayDeque<>();
Map<String, Integer> countParents = countParents(graph);
for (Map.Entry<String, Integer> entry : countParents.entrySet()) {
if (entry.getValue() == 0)
queue.add(entry.getKey());
}
while (queue.size() > 0) {
String current = queue.poll();
result.add(current);
for (String child : graph.get(current)) {
countParents.put(child, countParents.get(child) - 1);
if (countParents.get(child) == 0) {
queue.add(child);
}
}
}
return (graph.size() == result.size()) ? result : null;
}Can someone explain why the time complexity is n+m rather than n*m? Each time we pop from the cue we need to loop over all the requirements, meaning for each n (tasks) we do the full loop of m (requirements)
I didn’t use a queue in my solution, I directly deleted the keys from the card instead. It’s a bit tricky but it works very well:
std::map<std::string, int> count_reqs(std::vector<std::string> &tasks, std::vector<std::vector<std::string>> &requirements) {
std::map<std::string, int> res;
for (const auto &t : tasks) {
res[t] = 0;
}
for (const auto &req : requirements) {
++res[req[1]];
}
return res;
}
std::vector<std::string> task_scheduling(std::vector<std::string> tasks, std::vector<std::vector<std::string>> requirements) {
std::vector<std::string> res;
std::map<std::string, int> counts = count_reqs(tasks, requirements);
while (counts.size()) {
for (std::map<std::string, int>::iterator it = counts.begin(); it != counts.end(); ) {
if (it->second == 0) {
res.push_back(it->first);
for (const auto &req : requirements) {
if (req[0] == it->first) --counts[req[1]];
}
counts.erase(it++);
} else
++it;
}
}
return res;
}
You do not need to loop over all the requirements after you pop from the queue. You only need to loop over all the outgoing edges from the current vertex after popping that vertex from the queue, so that you can decrement the “incoming” count of each edge.
For the JS (and maybe other solutions) any reason to use a Map instead of simple object/hashmap data type, considering we don’t ever iterate over either of the maps? I feel it makes it a lot less readable to use Map, so prefer object if there’s not a meaningful performance difference.
Here’s a solution with objects that seems more readable to me:
function taskScheduling(tasks, requirements) {
const inDegrees = {};
const dependents = {};
for (const task of tasks) {
inDegrees[task] = 0;
dependents[task] = [];
}
for (let i = 0; i < requirements.length; i++) {
const parent = requirements[i][0];
const child = requirements[i][1];
inDegrees[child] += 1
dependents[parent].push(child)
}
const q = [];
for (const task of tasks) {
if (inDegrees[task] === 0) {
q.push(task);
}
}
const ans = [];
while (q.length > 0) {
const task = q.shift();
ans.push(task);
for (const dependentTask of dependents[task]) {
inDegrees[dependentTask] -= 1;
if (inDegrees[dependentTask] === 0) {
q.push(dependentTask);
}
}
}
return ans;
}
You are so smart with this answer!
from collections import defaultdict, deque
def task_scheduling(tasks: List[str], requirements: List[List[str]]) -> List[str]:
node_to_parents = defaultdict(set)
node_to_children = defaultdict(set)
for parent, node in requirements:
node_to_parents[node].add(parent)
node_to_children[parent].add(node)
queue = deque([node for node in tasks if node not in node_to_parents])
task_order = []
while queue:
node = queue.popleft()
task_order.append(node)
for child in node_to_children[node]:
node_to_parents[child].remove(node)
if not node_to_parents[child]:
queue.append(child)
return task_order