1. Problem Definition
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.
2. Problem Description
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:
tasks = [
(1, 3, [2]), // Task 1 can start after Task 2 is completed
(2, 2, []), // Task 2 can be performed independently
(3, 4, [1, 2]) // Task 3 can start after Tasks 1 and 2 are completed
]
Input Format
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.
Output Format
Output an integer representing the minimum time required to complete all tasks.
3. Solution Process
To solve this problem, we will follow these procedures.
- Creating the Dependency Graph: Represent the dependencies between tasks in the form of a graph.
- Finding the Longest Path: Use Depth-First Search (DFS) to find the longest path in order to calculate the start time of each task.
- Calculating the Final Time: Calculate the time required to complete all tasks.
3-1. Creating the Dependency Graph
First, we transform the input tasks into a graph structure. Each task is represented as a node, and the dependencies are represented as edges.
3-2. Finding the Longest Path
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.
3-3. Calculating the Final Time
Based on the time required to complete all tasks, we determine the completion time of the final task to calculate the minimum time.
4. Swift Code Implementation
Below is the Swift code based on the algorithm above.
import Foundation
struct Task {
let id: Int
let time: Int
let dependencies: [Int]
}
func minimumCompletionTime(tasks: [Task]) -> Int {
var graph = [Int: [Int]]() // Dependency graph
var inDegree = [Int: Int]() // In-degree
var completionTime = [Int: Int]() // Store completion time
// Initialize the graph and in-degrees
for task in tasks {
graph[task.id] = []
inDegree[task.id] = task.dependencies.count
completionTime[task.id] = 0
}
// Create the graph
for task in tasks {
for dependency in task.dependencies {
graph[dependency]?.append(task.id)
}
}
var queue = [Int]() // Tasks that can start
for task in tasks {
if inDegree[task.id] == 0 {
queue.append(task.id)
completionTime[task.id] = task.time // Initialize the time for independent tasks
}
}
var maxCompletionTime = 0
// Queue for topological sorting
while !queue.isEmpty {
let currentTaskId = queue.removeFirst()
let currentTaskTime = completionTime[currentTaskId]!
// Visit child tasks of the current task
for dependentTaskId in graph[currentTaskId]! {
completionTime[dependentTaskId] = max(completionTime[dependentTaskId]!, currentTaskTime + tasks.first { $0.id == dependentTaskId }!.time)
// Decrease the in-degree
inDegree[dependentTaskId]! -= 1
// Add to the queue if the in-degree is 0
if inDegree[dependentTaskId] == 0 {
queue.append(dependentTaskId)
}
}
maxCompletionTime = max(maxCompletionTime, currentTaskTime)
}
return maxCompletionTime
}
// Test case
let tasks = [
Task(id: 1, time: 3, dependencies: [2]),
Task(id: 2, time: 2, dependencies: []),
Task(id: 3, time: 4, dependencies: [1, 2])
]
let result = minimumCompletionTime(tasks: tasks)
print("Minimum time required to complete all tasks: \(result) seconds")
5. Code Explanation
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.
6. Conclusion
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!