The critical path problem is an important problem in graph theory, which calculates the minimum time required to complete a given set of tasks. Each task has a structure of dependencies on other tasks, which determines the execution order of the tasks. Through this problem, we need to create an optimal schedule that considers the dependencies between tasks.<\/p>\n
Based on the given list of tasks and the execution time of each task, calculate the minimum time required to complete all tasks. The tasks are given in the following format:<\/p>\n
\n tasks = [\n (1, 3, [2]), \/\/ Task 1 can start after Task 2 is completed\n (2, 2, []), \/\/ Task 2 can be performed independently\n (3, 4, [1, 2]) \/\/ Task 3 can start after Tasks 1 and 2 are completed\n ]\n <\/code><\/pre>\nInput Format<\/h3>\n
Each task is composed of a tuple, where the first element is the task ID, the second element is the execution time of the task, and the third element is a list of task IDs that it depends on.<\/p>\n
Output Format<\/h3>\n
Output an integer representing the minimum time required to complete all tasks.<\/p>\n
3. Solution Process<\/h2>\n
To solve this problem, we will follow these procedures.<\/p>\n
\n- Creating the Dependency Graph:<\/strong> Represent the dependencies between tasks in the form of a graph.<\/li>\n
- Finding the Longest Path:<\/strong> Use Depth-First Search (DFS) to find the longest path in order to calculate the start time of each task.<\/li>\n
- Calculating the Final Time:<\/strong> Calculate the time required to complete all tasks.<\/li>\n<\/ol>\n
3-1. Creating the Dependency Graph<\/h3>\n
First, we transform the input tasks into a graph structure. Each task is represented as a node, and the dependencies are represented as edges.<\/p>\n
3-2. Finding the Longest Path<\/h3>\n
Using depth-first search, we determine the timing for when each task can start. We record the start time of the task considering when its dependency tasks are finished. Then, we must visit all tasks to find the longest path.<\/p>\n
3-3. Calculating the Final Time<\/h3>\n
Based on the time required to complete all tasks, we determine the completion time of the final task to calculate the minimum time.<\/p>\n
4. Swift Code Implementation<\/h2>\n
Below is the Swift code based on the algorithm above.<\/p>\n
\n import Foundation\n\n struct Task {\n let id: Int\n let time: Int\n let dependencies: [Int]\n }\n\n func minimumCompletionTime(tasks: [Task]) -> Int {\n var graph = [Int: [Int]]() \/\/ Dependency graph\n var inDegree = [Int: Int]() \/\/ In-degree\n var completionTime = [Int: Int]() \/\/ Store completion time\n\n \/\/ Initialize the graph and in-degrees\n for task in tasks {\n graph[task.id] = []\n inDegree[task.id] = task.dependencies.count\n completionTime[task.id] = 0\n }\n\n \/\/ Create the graph\n for task in tasks {\n for dependency in task.dependencies {\n graph[dependency]?.append(task.id)\n }\n }\n\n var queue = [Int]() \/\/ Tasks that can start\n for task in tasks {\n if inDegree[task.id] == 0 {\n queue.append(task.id)\n completionTime[task.id] = task.time \/\/ Initialize the time for independent tasks\n }\n }\n\n var maxCompletionTime = 0\n\n \/\/ Queue for topological sorting\n while !queue.isEmpty {\n let currentTaskId = queue.removeFirst()\n let currentTaskTime = completionTime[currentTaskId]!\n\n \/\/ Visit child tasks of the current task\n for dependentTaskId in graph[currentTaskId]! {\n completionTime[dependentTaskId] = max(completionTime[dependentTaskId]!, currentTaskTime + tasks.first { $0.id == dependentTaskId }!.time)\n\n \/\/ Decrease the in-degree\n inDegree[dependentTaskId]! -= 1\n \/\/ Add to the queue if the in-degree is 0\n if inDegree[dependentTaskId] == 0 {\n queue.append(dependentTaskId)\n }\n }\n maxCompletionTime = max(maxCompletionTime, currentTaskTime)\n }\n\n return maxCompletionTime\n }\n\n \/\/ Test case\n let tasks = [\n Task(id: 1, time: 3, dependencies: [2]),\n Task(id: 2, time: 2, dependencies: []),\n Task(id: 3, time: 4, dependencies: [1, 2])\n ]\n\n let result = minimumCompletionTime(tasks: tasks)\n print(\"Minimum time required to complete all tasks: \\(result) seconds\")\n <\/code><\/pre>\n5. Code Explanation<\/h2>\n
The code above constructs a graph to solve the critical path problem and calculates the completion time for each task through depth-first search. It checks the dependencies for each task, updating completion times, and ultimately outputs the minimum time needed to complete all tasks.<\/p>\n
6. Conclusion<\/h2>\n
The critical path problem is an important algorithmic problem for managing dependencies between tasks. By solving this problem, one can enhance their understanding of graph theory, and it is also a frequently posed type in coding tests. Let’s practice various forms of problems based on the methods described above!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"