Swift Coding Test Course, Finding the Critical Path

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.

1. Creating the Dependency Graph: Represent the dependencies between tasks in the form of a graph.
2. Finding the Longest Path: Use Depth-First Search (DFS) to find the longest path in order to calculate the start time of each task.
3. 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!