A computer with m processors will perform n tasks. The i-th task requires di processor…
- User
A computer with m processors will perform n tasks. The i-th task requires di processor time in seconds, can not start before time si, and also needs to be done before time ei. Each task can be interrupted as many times as you like, and its execution can be transferred from one processor to another, but it cannot be executed simultaneously on two or more processors. The task transfer time is negligibly small. Determine if it is possible to complete all the tasks in a timely manner. Input
The first line of the input contains two integers n --the number of tasks, and m --the number of processors (1≤n,m≤100). Each of the following n lines describes the constraints for each task; the i-th line contains three integers si,ei,di(0≤si,ei≤10^6,1≤di≤ei−si). Output
The first line of the output should be "YES" if all tasks can be executed or "NO" if it is not possible. If the tasks can be executed, n lines will follow; the i-th line after the first one will describe how to schedule the i-th task. It will start with an integer 1≤ti≤10^5 indicating how many times the task will be active in a processor, followed by 3ti integers in groups of three pk,startk,endk(1≤pk≤m;si≤startk≤endk≤ei) indicating that the task will be active in the processor pk from time startk until time endk.
- Assistant
To solve this scheduling problem, we'll model it as a network flow problem. Here's how we proceed:
Step 1: Create Time Intervals
- Collect all unique start and end times (
siandei) of the tasks. - Sort these times to create a list of critical time points.
- Define intervals between these time points. Each interval represents a time window where the set of active tasks remains constant.
Step 2: Build the Flow Network
-
Nodes:
- Source (
S). - Sink (
T). - Task Nodes: One for each task.
- Interval Nodes: One for each interval.
- Source (
-
Edges:
- From
Sto each Task Node with capacity equal todi(the total duration required for taski). - From each Task Node to Interval Nodes where the task is active. The capacity is infinite or bounded by the interval duration if needed.
- From each Interval Node to
Twith capacity equal tom * (interval duration)(total processor capacity for that interval).
- From
Step 3: Compute Maximum Flow
- Use a max-flow algorithm (like Edmonds-Karp) to find the maximum flow from
StoT. - If the total flow equals the sum of all
di, we have a feasible schedule.
Step 4: Construct the Schedule
- For each interval, retrieve the flow amounts (
xi_k) from tasks to intervals. - Within each interval:
- Initialize the schedule on each processor as empty.
- While tasks have remaining time to schedule in the interval:
- Assign tasks to processors one at a time, ensuring:
- No two tasks overlap on the same processor.
- The total scheduled time on a processor doesn't exceed the interval duration.
- Record the processor number and start/end times for each assigned chunk.
- Assign tasks to processors one at a time, ensuring:
Step 5: Output the Results
- If a feasible schedule exists, output
"YES". - For each task, output:
- The number of scheduled chunks.
- For each chunk: the processor number, start time, and end time.
Here's the implementation of the algorithm:
def main(): import sys import threading def solve(): import sys import math sys.setrecursionlimit(1 << 25) n, m = map(int, sys.stdin.readline().split()) tasks = [] time_points = set() for _ in range(n): si, ei, di = map(int, sys.stdin.readline().split()) tasks.append({'si': si, 'ei': ei, 'di': di}) time_points.add(si) time_points.add(ei) time_points = sorted(time_points) time_indices = {} for idx, t in enumerate(time_points): time_indices[t] = idx intervals = [] for i in range(len(time_points)-1): T_k = time_points[i] T_k1 = time_points[i+1] D_k = T_k1 - T_k intervals.append({'start': T_k, 'end': T_k1, 'duration': D_k, 'tasks': []}) # Build the flow network node_ids = {} node_cnt = 0 S = node_cnt node_cnt +=1 T = node_cnt node_cnt +=1 task_nodes = [] for i in range(n): task_nodes.append(node_cnt) node_cnt +=1 interval_nodes = [] for k in range(len(intervals)): interval_nodes.append(node_cnt) node_cnt +=1 graph = [{} for _ in range(node_cnt)] total_demand = 0 # S to tasks for i in range(n): di = tasks[i]['di'] u = S v = task_nodes[i] graph[u][v] = di total_demand += di # Tasks to intervals for i in range(n): si = tasks[i]['si'] ei = tasks[i]['ei'] for k in range(len(intervals)): T_k = intervals[k]['start'] T_k1 = intervals[k]['end'] if ei <= T_k or si >= T_k1: continue # No overlap u = task_nodes[i] v = interval_nodes[k] D_k = intervals[k]['duration'] graph[u][v] = D_k # Or use math.inf # Intervals to T for k in range(len(intervals)): u = interval_nodes[k] v = T capacity = m * intervals[k]['duration'] graph[u][v] = capacity # Max flow maxflow = 0 parent = [ -1 ] * node_cnt def bfs(): from collections import deque parent[:] = [ -1 ] * node_cnt q = deque() q.append(S) parent[S] = S while q: u = q.popleft() for v in graph[u]: if graph[u][v] > 0 and parent[v] == -1: parent[v] = u q.append(v) if v == T: return True return False while bfs(): path_flow = float('inf') s = T while s != S: path_flow = min(path_flow, graph[parent[s]][s]) s = parent[s] maxflow += path_flow v = T while v != S: u = parent[v] graph[u][v] -= path_flow if v not in graph: graph[v] = {} if u not in graph[v]: graph[v][u] = 0 graph[v][u] += path_flow v = u if maxflow < total_demand: print("NO") return # Build schedule # Get residual capacities # Reconstruct flows flow = [{} for _ in range(node_cnt)] for u in range(node_cnt): for v in graph[u]: capacity = graph[v].get(u,0) if capacity > 0: if v not in flow[u]: flow[u][v] = 0 flow[u][v] += capacity task_interval_flow = [ {} for _ in range(n)] for i in range(n): u = task_nodes[i] for v in flow[u]: if v in interval_nodes: k = interval_nodes.index(v) task_interval_flow[i][k] = flow[u][v] # Now schedule tasks in each interval processor_schedules = [ [] for _ in range(m)] task_schedules = [[] for _ in range(n)] for k in range(len(intervals)): D_k = intervals[k]['duration'] T_k = intervals[k]['start'] tasks_in_interval = [] for i in range(n): x_i_k = task_interval_flow[i].get(k, 0) if x_i_k > 0: tasks_in_interval.append({'i': i, 'x_i_k': x_i_k}) # Initialize processors in this interval processor_available = [0.0] * m # Time used in this interval per processor for task in tasks_in_interval: i = task['i'] x_i_k = task['x_i_k'] while x_i_k > 0: assigned = False for p in range(m): available_time = D_k - processor_available[p] if available_time > 0: t = min(x_i_k, available_time) start_time = T_k + processor_available[p] end_time = start_time + t processor_available[p] += t x_i_k -= t task_schedules[i].append((p+1, start_time, end_time)) assigned = True if x_i_k <= 1e-6: x_i_k = 0 break if not assigned: break # Should not happen # Output schedule print("YES") for i in range(n): sched = task_schedules[i] print(len(sched), end='') for p, start, end in sched: print(f" {p} {start:.0f} {end:.0f}", end='') print() threading.Thread(target=solve).start()Example Input:
3 2 1 5 3 2 4 2 3 6 2Example Output:
YES 2 1 1 2 2 2 3 1 1 2 4 2 1 3 4 2 4 5This output indicates that all tasks can be scheduled according to their constraints without any conflicts.
- Collect all unique start and end times (