Consider the following problem:
The Searcy Wood Shop has a backlog of orders for its world famous rocking chair (1 chair per order). The total time required to make a chair is 1 week. However, since the chairs are sold in different regions and various markets, the amount of profit for each order may differ. In addition, there is a deadline associated with each order. The company will only earn a profit if they meet the deadline; otherwise, the profit is 0. Write a program that will determine an optimal schedule for the orders that will maximize profit.
The first line in a test case will contain an integer, n (0 ≤ n ≤ 1000), that represents the number of orders that are pending. A value of 0 for n indicates the end of the input file. The next n lines contain 3 positive integers each. The first integer, i, is an order number. All order numbers for a given test case are unique. The second integer represents the number of weeks from now until the deadline for order number i. The third integer represents the amount of profit that the company will earn if the deadline is met for order number i.
Example input:
7
1 3 40
2 1 35
3 1 30
4 3 25
5 1 20
6 3 15
7 2 10
4
3054 2 30
4099 1 35
3059 2 25
2098 1 40
0
Ouput:
100
70
The output will be the optimal sum of the input of the test case.
The problem that I am having is that I am struggling to come up with an algorithm that consistently finds this optimal sum.
My first idea was that I could simply go through each input week by week and choose the chair with the highest profit for said week. This didn't work though in the case that a week has two chairs that both have a higher profit than the week prior.
My next idea was that I could order the list in order from highest to lowest profit. Then I would go through the list from the highest profit and compare the current entry to the next entry and choose the entry with the lower week.
None of these are consistently working. Can anyone help me?
CodePudding user response：
Firstly you'll have to think which orders are eligible to be completed on the 'ith' day, that would be all the orders with deadline greater than or equal to i. So just iterate all the orders in decreasing order of their deadline.
Lets say the last deadline week is 'x' then push all the profit values of week 'x' in a priority queue. The max value from the pushed values would be your optimal profit for week 'x'. Now remove the selected profit from the priority queue and add it to your answer. The remaining values are still eligible to be used in the previous weeks and now add the profit values with deadline 'x-1' to the priority queue and take the max out of them and repeat until deadline week becomes 0.
CodePudding user response：
I would first sort the list by second column (number of weeks before the deadline) in increasing order and then sort the third column (profit) in decreasing order.
For example, in your file:
2098 1 40
2 1 35
4099 1 35
3 1 30
5 1 20
3054 2 30
3059 2 25
7 2 10
1 3 40
4 3 25
6 3 15
Among the same number of week orders, I will peak the highest profit to execute. If deadline is 1 week - top highest order; 2 weeks - 2 top highest orders, 3 weeks - 3 top highest orders and so on.