Pairs Topics | Algorithms Question | HackerRank
A greedy algorithm is an algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
A very common problem which gives good insight into this is the Job Scheduling Problem.
You have jobs numbered and you have the start times and the end times for the job. Which jobs should you choose such that you get the maximal set of non-overlapping jobs?
The correct solution to this problem is to sort all the jobs on the basis of their end times and then keep on selecting the job with the minimal index in this list which does not overlap with currently selected jobs.
Sounds intuitive, but why does it work?
Well, since each job has equal weight, selecting the one which makes way for newer jobs sooner is optimal. Although a more formal argument can be made for a rigorous proof, the intuition behind it is similar.
Now, let's consider another problem. You again have jobs. Each job can be completed at any time and takes time to complete and has a point value of . But with each second, the point value of the job decreases by . If you have to complete all the jobs, what is the maximum points that you can get?
The problem basically asks us for an order of accomplishing the jobs.
Here, doing the job with higher first makes sense. At the same time, doing the job with lower also sounds good. So how do we decide?
Assume you have just jobs which, without loss of generality, can be numbered as and .
Now, if you do job before job , your net score is:
Read full article from Pairs Topics | Algorithms Question | HackerRank
No comments:
Post a Comment