Assume you are given n tasks each of which takes the same, unit amount of time t
ID: 3822711 • Letter: A
Question
Assume you are given n tasks each of which takes the same, unit amount of time to complete. Each task has an integer deadline and penalty associated with it which you pay if you do not complete the task in time. Design an algorithm that schedules the tasks so that the total penalty you have to pay is as small as possible. You have to write a very long paper. You compiled a sequence of books in the order you will need them, some of them multiple times. Such a sequence might look something like this: B_1, B_2, B_1, B_3, B_4, B_5, B_2, B_6, B_4 B_1, B_7, ... Unfortunately, the library lets you keep at most 10 books at home at any moment so every now and then you have to make a trip to the library to exchange books. On each trip you can exchange any number of books (of course, between 1 and all of 10 books you can keep at home). Design an algorithm which decides which books to exchange on each library trip so that the total number of trips which you will have to make to the library is as small as possible.Explanation / Answer
Hi,I have answered Q1.
Please repost other question in separate post.
1) Sort all tasks in decreasing order of penalty.
2) Initialize the result sequence as first task in sorted tasks.
3) Do following for remaining n-1 tasks
.......a) If the current task can fit in the current result sequence
without missing the deadline, add current task to the result.
Else ignore the current task.
// A structure to represent a Task
struct Task
{
char id; // Task Id
int dead; // Deadline of Task
int penalty; // penalty if Task is over before or on deadline
};
// This function is used for sorting all Tasks according to penalty
bool comparison(Task a, Task b)
{
return (a.penalty > b.penalty);
}
// Returns minimum number of platforms reqquired
void printTaskScheduling(Task arr[], int n)
{
// Sort all Tasks according to decreasing order of penalty
sort(arr, arr+n, comparison);
int result[n]; // To store result (Sequence of Tasks)
bool slot[n]; // To keep track of free time slots
// Initialize all slots to be free
for (int i=0; i<n; i++)
slot[i] = false;
// Iterate through all given Tasks
for (int i=0; i<n; i++)
{
// Find a free slot for this Task (Note that we start
// from the last possible slot)
for (int j=min(n, arr[i].dead)-1; j>=0; j--)
{
// Free slot found
if (slot[j]==false)
{
result[j] = i; // Add this Task to result
slot[j] = true; // Make this slot occupied
break;
}
}
}
// Print the result
for (int i=0; i<n; i++)
if (slot[i])
cout << arr[result[i]].id << " ";
}