vats.manthan3's blog

Job Sequencing Problem--help
By vats.manthan3, history, 3 years 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

Comments Comments (1)
| Write comment?
»
3 years 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.

→ Reply