vats.manthan3's blog

By vats.manthan3, history, 2 months ago, In English

This is the problem on geeksforgeeks job sequencing problem. This problem requires greedy approach..

So in the particular problem,it is asked to find maximum jobs possible and maximum profit, if each job takes 1 unit time and must be completed by its deadline... So input format is (job id, deadline, profit).

My approach----

So basically what I did is I created a map<int,multiset> and I used deadline as Key and stored all given profits related to it in sorted order. While storing these values, I calculated Maximum deadline value among all deadline. Let it me max_val; Then I created a multiset final_jobs to store min( D , given jobs with deadline D ) largest profits for each deadline ( where D = deadline) i.e. among all jobs which have D = 1,I took largest value; for D = 2, I took 2 largest value if number of jobs with D = 2 is greater or equal to D = 2 and so on. After that I took M largest value from final_jobs and added them up. { where M = min( max_val, size of final_jobs )}..

But for few test-cases my solution is failing, I think My approach is correct and tried to debug but I am not able to find any error. I have one more approach in mind but until I don't find error in this approach I can't use other approach (it's against my norms).

My Solution

Could anyone just help me in finding errors in my approach and implementation...

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vats.manthan3 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can give you a test case on which your code will fail. Consider the following input -

8
1 1 100
2 2 100
3 3 100
4 3 100
5 3 100
6 4 1
7 5 1

In this test case, you have a total of 8 jobs. 6 jobs have a reward 100 but have deadlines up to day 3. the remaining two jobs have reward 1 each.

So, in the optimal case, you will be able to complete only 3 jobs up to day 3 and will have to do the 1 reward job on days 4 and 5. So you will earn a maximum of 302

Now let us see what your code does:- The multisets that you create will have the following values with the deadline as key —

1 -> {100}
2 -> {100, 100}
3 -> {100, 100, 100}
4 -> {1}
5 -> {1}

You will end up inserting them all into your final multiset and take the largest 5 values and hence will output 500 as the answer.

If you want help fixing your solution, then please feel free to ask. I just wanted to give you the chance to fix it yourself now that you have the failing test case.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks I tried the second approach and this is the code..Solution.

    Now its passing every test-case.. This time I create a vector<pair<int,int>> vec to store profits and deadlines in decreasing order according to profits and also stored Max deadline in variable max_val . Then I created a vector jobs(max_val,0) all initialised to 0 and then I traversed the vec and for every i if (jobs[t]==0) place vec[i].first, add value to profit ( where t = vec[i].second -1 ). And if condition fails then traverse back from t till >= 0 and if found jobs[t]==0 then do the same..

    Is this approach the optimal way to solve this problem or there are any other better approaches ??

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Hi can you help me with this approach ? It fails on a TC and I dont know why.

    Logic

    UPD : Got the mistake, I was calculating dp wrong. It should have been dp[i]=max(dp[i-1]+max with dl=i,dp[i-2]+top 2 with dl=i,.....).

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not sure how You implemented it but as you are stating, I think your logic will not give correct answer for the test-case which NoCodeNoLife has mentioned earlier... I might not be correct but in your approach,

      Your Logic

      what if there is only one job with deadline 2 then how will you select "top 2 elements with deadline =2" and if you mean "top 2 elements with deadline >=2", then you will end up doing something similar to my first logic... If I am not getting your logic right, apology for that and show me the code.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry I didn't see your updated message...Could you please provide your code, I want to see your code as well for a greater sight..