英文:
Linked Objects & Task Count
问题
以下是已翻译好的部分：
"一个对象的任务可以与另一个对象一起运行，如果是这种情况，主链接对象将不会运行自己的任务（与每个与其链接的对象相比，是联合而不是独立运行）。
假设我有以下需要运行的任务，答案应为4个任务。
- 一个
- 二（与一个链接）
- 三
- 四（与三链接）
- 五（与三链接）
- 六
将有4个任务（其中3个与链接对象一起运行，而不是独立运行）。所以是1个（一个 + 二）和1个（三 + 四）和1个（三 + 五）和1个（六）。
我尝试了不同的示例，但无法弄清楚如何计算所需的任务数量。
另一个示例：
- 一个
- 二（与一个链接）
- 三
- 四（与三链接）
- 五
在这种情况下，必须是1个（一个 + 二）和1个（三 + 四）和1个（五）= 3个任务。"
英文:
Tasks for one object can be run coupled with another and if that is the case the primary linked object will not run it's own task (coupled instead of solo for every object that is linked to it).
Say I have the following tasks I need to run, I need the answer to be 4 tasks.
- One
- Two (linked to One)
- Three
- Four (linked to Three)
- Five (linked to Three)
- Six
There will be 4 tasks (3 of which are run with the linked object as 1 instead of 2). So 1 (One + Two) & 1 (Three + Four) & 1 (Three + Five) & 1 (Six).
I have tried different examples but cannot figure out how to compute the number of tasks required.
Another example:
- One
- Two (linked to One)
- Three
- Four (linked to Three)
- Five
In this case it has to be 1 (One + Two) & 1 (Three + Four) & 1 (Five) = 3 tasks.
答案1
得分: 1
这是一个图问题。第一个示例可以可视化为：
(_root_)
/ | \
一 三 六
/ / \
二 四 五
第二个示例：
(_root_)
/ | \
一 三 五
/ |
二 四
解决方案包括列出所有叶节点（如果需要，列出从根到每个叶节点的路径上的节点列表）。
所以：
-
从输入中的节点和边信息创建树（根节点隐式定义）
-
使用深度优先遍历遍历树，以找到所有（路径到）叶节点。
英文:
This is a graph problem. The first example can be visualised as:
(_root_)
/ | \
One Three Six
/ / \
Two Four Five
The second example:
(_root_)
/ | \
One Three Five
/ |
Two Four
The solution consists of listing all leaf-nodes (and if needed, the list of nodes on the path from the root to each leaf).
So:
-
Create the tree from the node and edge information you have in the input (the root is implicitly defined)
-
Traverse the tree with a depth-first traversal to find all (paths to) leaf nodes.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论