Untitled
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
#!/usr/bin/env python3
import heapq
from collections import defaultdict
def PriorityTaskScheduler(strArr):
"""
Simulates a priority-based CPU scheduler to calculate the average wait time
for each priority level.
Time Complexity: O(N log N) - Dominated by sorting the initial jobs and heap operations.
Space Complexity: O(N) - To store the parsed jobs and the priority queue.
"""
jobs = strArr
if not jobs:
return []
parsed_jobs = []
for job_string in jobs:
try:
_job_id, submit, process, prio = job_string.split(',')
parsed_jobs.append([int(submit), int(process), int(prio)])
except (ValueError, IndexError):
continue
parsed_jobs.sort()
current_time = 0
job_index = 0
num_jobs = len(parsed_jobs)
priority_stats = defaultdict(lambda: [0, 0])
wait_queue = []
processed_count = 0
while processed_count < num_jobs:
while job_index < num_jobs and parsed_jobs[job_index][0] <= current_time:
submit_time, process_time, priority = parsed_jobs[job_index]
heapq.heappush(wait_queue, (-priority, submit_time, process_time))
job_index += 1
if wait_queue:
neg_priority, submit_time, process_time = heapq.heappop(wait_queue)
priority = -neg_priority
wait_time = current_time - submit_time
priority_stats[priority][0] += wait_time
priority_stats[priority][1] += 1
current_time += process_time
processed_count += 1
else:
if job_index < num_jobs:
current_time = parsed_jobs[job_index][0]
output = []
sorted_priorities = sorted(priority_stats.keys(), reverse=True)
for priority in sorted_priorities:
total_wait, count = priority_stats[priority]
avg_wait = total_wait // count
output.append(f"Priority-{priority}: {avg_wait}")
return output
data = [
"jobA,0,10,3\njobB,2,5,1\njobC,3,8,3\njobD,7,4,2\n",
"jobB,2,5,1\njobA,0,10,3\njobC,3,8,3\njobD,7,4,2\njobE,20,4,3",
"jobA,0,5,1\njobB,100,10,5\njobC,101,5,5",
]
for d in data:
print(PriorityTaskScheduler(d.split("\n")))
Python
INFO