Given a set of N jobs where each jobi has a deadline and profit associated with it.Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit associated with job if and only if the job is completed by its deadline.Find the number of jobs done and the maximum profit.Note: Jobs will be given in the form (Jobid, Deadline, Profit) associated with that Job.
Question
Given a set of N jobs where each jobi has a deadline and profit associated with it.Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit associated with job if and only if the job is completed by its deadline.Find the number of jobs done and the maximum profit.Note: Jobs will be given in the form (Jobid, Deadline, Profit) associated with that Job.
Solution
This problem can be solved using a greedy approach. Here are the steps:
- Sort all jobs in decreasing order of profit.
- Initialize the result sequence as the first job in sorted jobs.
- Do the following for the remaining jobs:
- If the current job can fit in the current result sequence without missing the deadline, add the current job to the result. Else ignore the current job.
Here is a Python code snippet that implements the above steps:
def printJobScheduling(arr, t):
n = len(arr)
# Step 1: Sort all jobs according to
# decreasing order of profit
for i in range(n):
for j in range(n - 1 - i):
if arr[j][2] < arr[j + 1][2]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# To keep track of free time slots
result = [False] * t
# To store result (Sequence of jobs)
job = ['-1'] * t
# Iterate through all given jobs
for i in range(len(arr)):
# Find a free slot for this job
# (Note that we start from the
# last possible slot)
for j in range(min(t - 1, arr[i][1] - 1), -1, -1):
# Free slot found
if result[j] is False:
result[j] = True
job[j] = arr[i][0]
break
# print the sequence
print(job)
In this code, arr is the array of jobs with each job represented as a tuple of (Jobid, Deadline, Profit). The function printJobScheduling prints the maximum profit sequence of jobs.
The time complexity of this code is O(n^2) where n is the number of jobs. This is because we are sorting the jobs and then for each job, we are finding a free slot.
Similar Questions
A plant manager is attempting to determine the production schedule of various products to maximize profit. Assume that a machine hour constraint is binding. If the original amount of machine hours available is 200 minutes, and the range of feasibility is from 130 minutes to 300 minutes, providing two additional machine hours will result in:Group of answer choicesthe same product mix, same total profit.a different product mix, different total profit.the same product mix, different total profit.a different product mix, same total profit as before.
You are given a job that has been divided into N tasks. The task cannot be divided any further. Each of the N tasks takes Si number of seconds to complete. Your job will be completed when all your tasks are completed. You have K workers at your disposal to help you complete the tasks. But as per the nature of the job, a worker can only be allocated continuous tasks. A worker can work only on a single task at any given point in time. However, the workers can work in parallel on different tasks. You have to find the minimum possible time in which you can complete the job.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines. The first line of each test case contains N and K - the number of tasks and available workers for the current job, separated by space. The next line contains N positive integers - denoting the time taken to complete the ith task.Output FormatFor each test case, print the minimum possible time in which you can complete the job, separated by a new line.Constraints50 points1 <= N,K <= 20100 points1 <= N,K <= 10000General Constraints1 <= T <= 501 <= Si <= 103ExampleInput610 31 10 13 4 5 12 23 12 18 88 417 27 22 45 26 32 45 162 274 617 374 24 61 81 66 76 512 154 104 215 30 10 50Output3866741596455ExplanationTest Case 1: The arrangement for which we can achieve minimum possible time is as follows:[1 10 13 4 5] - Worker 1[12 23] - Worker 2[12 18 8] - Worker 3Test Case 2: The arrangement for which we can achieve minimum possible time is as follows:[17 27 22] - Worker 1[45] - Worker 2[26 32] - Worker 3
Maximum ProfitSay you have an array, A, for which the ith element is the price of a given stock on day i.Design an algorithm to find the maximum profit. You may complete at most 2 transactions.Return the maximum possible profit.Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).Problem Constraints1 <= length(A) <= 7e51 <= A[i] <= 1e7Sample input57 2 4 8 7Sample output6ExplanationInput: 57 2 4 8 7The first line contains the number of elements in the array.And, the second line contains the element of array.Output:6
A business owner makes 50 items by hand in 40 hours. She could have earned $20 an hour working for someone else. Her total explicit costs are $200. If each item she makes sells for $15, her economic profit equals:
The organizer of a sports event estimates that if the event is announced 𝑥 days in advance, the revenueobtained will be 𝑅(𝑥) thousand dollars, where𝑅(𝑥) = 400 + 120𝑥 − 𝑥2The cost of advertising the event for 𝑥 days is 𝐶(𝑥) = 2𝑥2 + 300a. Find the profit function 𝑃(𝑥) = 𝑅(𝑥) − 𝐶(𝑥) and sketch its graph.b. How many days in advance should the event be announced in order to maximize profit? What is themaximum profit?c. What is the ratio of revenue to cost 𝑄(𝑥) = 𝑅(𝑥)𝐶(𝑥) at the optimal announcement time found in part (b)?What happens to this ratio as 𝑥 → 0? Interpret these results
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.