kotlin coding test course, finding the critical path

Problem Definition

This problem involves finding the critical path from a start node to a finish node in a given connected graph. The critical path indicates the minimum time or distance required to perform the tasks in the graph and plays a key role in project management and optimal resource allocation.

For example, assume a diagram is given that represents the time required to complete each task. There may be conditions that other tasks must be completed first for each task to be completed. The problem can be solved using a Directed Acyclic Graph (DAG) that reflects these conditions.

Input Format

• The first line contains a natural number N (the number of tasks).
• The next N lines contain the task number, required time, and dependent task number separated by spaces. If there are no dependent tasks, it is indicated by -1.

Output Format

The length of the critical path (total time taken) is printed.

Example

Input

            5
            1 3 -1
            2 2 1
            3 1 1
            4 4 2
            5 2 3
            

Output

            9
            

Solution Process

To solve this problem, the following steps are followed:

1. Graph Modeling: Each task is represented as a node, and the dependencies are represented as edges to create a Directed Acyclic Graph (DAG).
2. Topological Sorting: To perform tasks along the edges, the dependencies must be considered. Therefore, topological sorting is performed to order the nodes.
3. Longest Path Calculation: Following the results of the topological sorting, the required times of each task are accumulated to calculate the longest path. The maximum value of the required times for the nodes is stored to derive the final result.

Kotlin Code Implementation

            fun main() {
                val n = readLine()!!.toInt()
                val time = IntArray(n + 1)
                val graph = Array(n + 1) { mutableListOf() }
                val indegree = IntArray(n + 1)
                
                for (i in 1..n) {
                    val input = readLine()!!.split(" ").map { it.toInt() }
                    time[i] = input[1]
                    if (input[2] != -1) {
                        graph[input[2]].add(i)
                        indegree[i]++
                    }
                }

                val dp = IntArray(n + 1)
                val queue: Queue = LinkedList()

                for (i in 1..n) {
                    if (indegree[i] == 0) {
                        queue.offer(i)
                        dp[i] = time[i]
                    }
                }

                while (queue.isNotEmpty()) {
                    val current = queue.poll()
                    for (next in graph[current]) {
                        dp[next] = maxOf(dp[next], dp[current] + time[next])
                        indegree[next]--
                        if (indegree[next] == 0) {
                            queue.offer(next)
                        }
                    }
                }

                println(dp.maxOrNull())
            }
            

Code Explanation

The above code consists of the following steps:

1. Read the number of tasks N.
2. Initialize an array time to store the execution times of tasks and an array graph to store the graph edges.
3. Read the dependency relationships of each task to set up the graph and the indegree.
4. Use a Queue to perform topological sorting and calculate the longest path. Accumulate the required times of each task in the dp array.
5. Print the result of the longest path.

Problem-Solving Strategy

The problem of finding the critical path is an important factor in time management in project management. Therefore, to solve such problems:

• Code Optimization: It is important to optimize the algorithm with performance considerations.
• Analysis and Planning: Systematically analyze the problem requirements and plan solutions.
• Practice Similar Problems: Gain experience and practice considering various situations through similar problems.