Question

There is an old fairy tale where some elves secretly help an old shoemaker finish his work for the day. In this version, the shoemaker and the elves collaborate openly Each day the shoemaker receives n orders for custom-made shoes. In the evening, n elves arrive to help him assemble the shoes. The shoemaker first cuts out the leather pieces for one pair of shoes. Then an elf stitches the pieces together to complete the shoes. For each i, let s, be the number of minutes the shoemaker takes to work on the ith pair and let e be the number of minutes an elf takes to complete the ith pair. Since there are enough elves, everyone can work in parallel. For example, the shoemaker can begin work on the second pair of shoes before the first elf has finished the first pair. In the following diagram, s1 3, e-5, 824, e2 8, 83- 9, e3 7, 84 2, e41. In the diagram, the shaded boxes represent the shoemaker working. The non-shaded boxes represent the elves. Notice that the shoemaker can work on the second pair of shoes, while the first elf is assembling the first pair Pair 1: 3 air Pair 3: Pair 4: 9 time in minutes For this problem we are concerned with when the last elf finishes. In the example above, the 3rd elf is the one to finish last. That means it took 3+4+9+7-23 minutes to finish making all pairs of shoes. On the other hand, if the shoemaker worked on the shoes in a different order, then total time can be reduced In the following ordering of the same shoes, the total time is only 4 +9+3+5-21 minutes Pair 2: air Pair 1: Pair 4: time in minutes > For this problem, you will prove that ordering the pairs by decreasing e, results in the smallest total time to finish all the pairs of shoes. Note that si and e, may not be correlated. In the example above, 81 82 but el > e2. Also, note that even in the optimum ordering the last elf to finish does not have to be en a. State and prove a "swapping lemma" for this greedy algorithm. Consider swapping adjacent pairs b. Use your swapping lemma to prove that the greedy algorithm which orders the pairs of shoes by decreasing e, results in the smallest total time to finish all pairs of shoes. Note: you must use arithmetic in an argument about finish times. Also, the finish time depends on both the Shoemaker's time and the elves' time Note: You must show that there does not exist an ordering of the pairs of shoes where the Shoemaker and the elves finish all n pairs of shoes earlier than if they followed the greedy algorithm. Do not appeal to any general principles. You must incorporate your swapping lemma above in the proof

Answer 1

#include <iostream>
#include <algorithm>
using namespace std;

struct job
{
int id;
int time;
int fine;
};

bool compFunction(job a, job b){ return (a.fine < b.fine); }

void jobSequence( job* arr, int n){
// Sort all jobs according to increasing order of fine
sort(arr, arr+n, compFunction);

int result[n]; // To store final sequence
bool slot[n]; // To check if slot is free

for(int i=0; i<n; i++){ slot[i] = false; }

for(int i=0; i<n; i++){
int from = n;
if( arr[i].time < from ){ from = arr[i].time; }
for (int j = from-1; j >= 0; j--){
if( slot[j]==false ){
result[j] = i;
slot[j] = true;
break;
}
}
}
for (int i=0; i<n; i++){
if( slot[i] ){ cout << arr[result[i]].id << " "; }}
cout << endl;
}

// Driver program to test methods
int main()
{
int totalJobs;
job* arr;
cin >> totalJobs;
arr = new job[totalJobs];
for(int i = 0; i < totalJobs; i++){
cin >> arr[i].time >> arr[i].fine;
arr[i].id = i+1;
}
jobSequence(arr, totalJobs);
return 0;
}