{"id":1417,"date":"2020-06-11T03:35:44","date_gmt":"2020-06-11T03:35:44","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1417"},"modified":"2022-03-30T23:02:10","modified_gmt":"2022-03-30T23:02:10","slug":"profit-priority","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/profit-priority\/","title":{"rendered":"PROFIT PRIORITY"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Greedy algorithm.<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

One day Aman went to the office and his boss gave him some tasks to finish within the given deadline and told him to earn maximum profit. Boss gave him a set of N task where each taski has a deadline and profit associated with it. Each task takes 1 unit of time to complete and only one job can be scheduled at a time. Aman can earn the profit if and only if the job is completed by its deadline. Aman has to find the maximum profit but he doesn’t know how to maximize profit so he asks for your help.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
7\n1 1 3\n2 3 5\n3 4 20\n4 3 18\n5 2 0\n6 1 6\n7 2 30\n\n74\n\nThe first task completed will be task-6 with a profit of 6.\nThe second task completed will be task-7 with a profit of 30.\nThe third task completed will be task-4 with a profit of 18.\nThe last task completed will be task-3 with a profit of 20.\nSo maximum profit = 6+30+18+20=74.<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
Input:  Five Jobs with following\ndeadlines and profits\n  ID   Deadline    Profit\n  x       2        100\n  y       1        19\n  z       2        27\n  u       1        25\n  v       3        15\nOutput: Following is maximum \nprofit sequence of jobs\n        z,x,v\n\nTo solve this problem, the given jobs are sorted according to their profit in a descending order.\nFrom the given jobs, first we select x, as it can be completed within its deadline and gives maximum profit.\n\nNext, z is selected as it gives more profit compared to y.\n\ny cannot be selected as its deadline is over.\n\nThe job u is discarded as it cannot be executed within its deadline.\n\nv is selected as it can be completed within its deadline.\n\nThus, the solution is the sequence of jobs (z,x,v), which are being completed within their deadline and give maximum profit.\n\nTotal profit 100+ 27+15 =142.<\/code><\/pre>\n
SOLVING APPROACH:<\/h3>\n
\n
This question is the famous job sequencing<\/em> problem which uses greedy approach .<\/p>\n
Since our objective is to select jobs that will give us higher profit,to solve this problem, the given jobs are sorted according to their profit in a descending order. <\/p>\n
We adopt a greedy algorithm to determine how the next job is selected for an optimal solution. The greedy algorithm described below always gives an optimal solution to the job sequencing problem.<\/p>\n
    \n
  1. \n
    Sort all the given jobs in the decreasing order of their profits.<\/p>\n<\/li>\n
  2. \n
    Iterate on jobs in decreasing order of profit.For each job , do the following :<\/p>\n<\/li>\n
  3. \n
    Find a time slot i, such that slot is empty and i >><\/p>\n<\/li>\n
  4. \n
    If no such i exists, then ignore the job.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t