В нашей системе данные обрабатываются процессами, которые выстраиваются в зависимости…
- User
В нашей системе данные обрабатываются процессами, которые выстраиваются в зависимости друг от друга. В системе находится n процессов, пронумерованных от 1 до n. Процесс с номером і сначала ждет завершения всех процессов, от которых он зависит, исполняется за ti секунд, после чего завершается. Вам предстоит определить, за какое минимальное время смогут завершиться все процессы. Минимальным временем считается то, которое достигается, когда планировщик процессов действует оптимально и имеет в распоряжении бесконечное количество вычислительных узлов, на которых, тем не менее, каждый процесс завершается строго за указанное ему время. В первой строке дано число п (1 ≤ n ≤ 10^5) — количество процессов. Далее дано n строк. В i-й строке первым числом идёт ti (0 ≤ ti ≤ 10^12) — время исполнения i-го процесса в секундах. Далее до конца строки идут номера процессов, от которых зависит процесс і. В единственной строке выведите одно число - минимальное время в секундах, за которое могут исполниться все процессы.
Пример 1 Ввод 5 10 2 3 5 5 4 0 4 15 3 Вывод 25
Пример 2 Ввод 6 2 2 2 3 15 4 1 5 2 76 0 Вывод 22
- Assistant
To solve this problem, we need to determine the minimum time required to execute all processes, considering their dependencies and execution times. Each process can only start after all of its dependencies have finished.
Here's a step-by-step solution:
-
Read Input and Build Process ID Mapping:
- Collect all unique process IDs, including those only mentioned in dependencies but not explicitly defined in the process list.
- Map each unique process ID to an index in a compact array to handle large IDs and optimize memory usage.
-
Initialize Data Structures:
- Create arrays to store execution times (
t_i), in-degrees (number of dependencies), and dependency lists for each process. - For processes not explicitly defined (only in dependencies), default their execution times to
0.
- Create arrays to store execution times (
-
Build the Dependency Graph:
- For each process, update the in-degree counts based on its dependencies.
- Build a reverse adjacency list (
adj_rev) whereadj_rev[dep]contains all processes that depend ondep.
-
Topological Sorting Using Kahn's Algorithm:
- Initialize a queue with all processes that have an in-degree of
0(no dependencies). - While the queue is not empty:
- Dequeue a process
i. - Calculate its earliest finish time:
earliest_finish_time[i] = earliest_start_time[i] + t_i. - For all processes
jthat depend oni, update their earliest start times and decrease their in-degree. - If a process
jnow has an in-degree of0, enqueue it.
- Dequeue a process
- Initialize a queue with all processes that have an in-degree of
-
Compute the Minimum Total Time:
- After processing all processes, the minimum total time is the maximum of all earliest finish times.
-
Edge Cases and Input Constraints:
- The total number of processes and dependencies (
N + M) won't exceed3e5. - Use appropriate data structures to handle large inputs efficiently (e.g.,
defaultdict, arrays).
- The total number of processes and dependencies (
Here's the code that implements the above solution:
from collections import deque, defaultdict import sys import threading def main(): import sys import math sys.setrecursionlimit(1 << 25) n = int(sys.stdin.readline()) total_dependencies = 0 process_ids = set() dependencies_list = [] t_dict = {} for _ in range(n): parts = sys.stdin.readline().split() t_i = int(parts[0]) deps = list(map(int, parts[1:])) total_dependencies += len(deps) process_ids.add(_+1) # Process IDs from 1 to n process_ids.update(deps) dependencies_list.append((_, t_i, deps)) t_dict[_+1] = t_i # Total number of unique process IDs process_ids = sorted(process_ids) id_to_idx = {pid: idx for idx, pid in enumerate(process_ids)} idx_to_id = {idx: pid for idx, pid in enumerate(process_ids)} N = len(process_ids) t = [0]*N in_degree = [0]*N adj_rev = [[] for _ in range(N)] earliest_start_time = [0]*N # Initialize t[i] for processes given in input # and set t[i]=0 for processes only appearing in dependencies for proc_idx, t_i, deps in dependencies_list: pid = proc_idx +1 idx = id_to_idx[pid] t[idx] = t_i for dep_pid in deps: dep_idx = id_to_idx[dep_pid] adj_rev[dep_idx].append(idx) in_degree[idx] +=1 # Initialize queue with processes with in-degree zero queue = deque() for idx in range(N): if in_degree[idx]==0: queue.append(idx) earliest_finish_time = [0]*N while queue: idx = queue.popleft() earliest_finish_time = earliest_start_time[idx] + t[idx] for j in adj_rev[idx]: # Update earliest_start_time[j] earliest_start_time[j] = max(earliest_start_time[j], earliest_finish_time) in_degree[j] -=1 if in_degree[j]==0: queue.append(j) # Find maximum earliest_finish_time among all processes min_total_time = 0 for idx in range(N): finish_time = earliest_start_time[idx] + t[idx] min_total_time = max(min_total_time, finish_time) print(int(min_total_time)) threading.Thread(target=main).start() -