WRIGHT STATE UNIVERSITY Department of Computer Science and Engineering
You are given n jobs where each job takes one unit of time and ith job provides a gain of gi (gi > 0) if completed on or before its integer deadline di. All jobs can start as early as time 0. For instance, first job can start at time 0 and end at time 1 in an optimal schedule. (Note that the algorithm generalizes to real number deadlines trivially so the restriction is for ease of I/O and enabling reliable equality checks.)
Design and implement an efficient algorithm to find a schedule (determining jobs and their end times) that maximizes the gain. (The start times are implicit.) Also provide a clear informal argument of correctness and computational complexity.
Assume that the input is given as a sequence of lines providing job id, job deadline, and job gain in that order. (The input jobs must be ordered in the descending order of gain as shown.)
1 4 20
2 2 15
3 2 15
4 1 10
5 3 5
The expected output schedule and total gain are given below. You must additionally print the input sorted by gain too as shown below for completeness.
Input Jobs, Deadlines and Gains (sorted by descending Gains)
1 4 20
2 2 15
3 2 15
4 1 10
5 3 5
Output Schedule by End Time (0 means not scheduled.)
1 4
2 2
3 1
4 0
5 3
Total Gain
55
TURNIN: Upload one tar/zip archive per team (with team member names and email addresses included on each file) that contains text files (e.g., README, source code file assignment2.py (with algorithm, informal argument of correctness, and computational complexity included as documentation), and sample inputs and outputs (in the format shown above, organized possibly in a separate directory/folder), to Assignment 2 DropBox on Pilot. Use the convention and instructions given in Assignment 1 for details and fill gaps. (Include only one submission per team – not one submission per person. Also, do not send redundant emails.)
Need Help and Solution?
Please contact for 100% Accurate and Plagiarism free Solution:
WhatsApp : +91 - 995 314 1035
Solution Includes: Plagiarism and AI report with 100% Accuracy.
