Shoemaker has N jobs (orders from customers) which he must make. Shoemaker can w

Question

Shoemaker has N jobs (orders from customers) which he must make. Shoemaker can work on only one job in each day. For each ith job, it is known the integer Ti (1<=Ti<=1000), the time in days it takes the shoemaker to finish the job. For each day of delay before starting to work for the ith job, shoemaker must pay a fine of Si (1<=Si<=10000) cents. Your task is to help the shoemaker. Write a program in Java or C++ to find the sequence of jobs with minimal total fine.

Input: First line of input contains an integer N (1<=N<=1000). The next N lines each contain two numbers: the time and fine of each task in order.

Output: Your program should print the sequence of jobs with minimal fine.

Sample input:

4

3 4

1 1000

2 2

5 5

Sample output:

Solve the problem using greedy algorithms.

Explanation / Answer

I have written the code, and tested again several different inputs. It is correct according to me, but doesn't satisfy the output you mentioned.

#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;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.