RENT - Rent your airplane and make money
"ABEAS Corp." is a very small company that owns a single airplane. The customers of ABEAS Corp are large airline companies which rent the airplane to accommodate occasional overcapacity.
Customers send renting orders that consist of a time interval and a price that the customer is ready to pay for renting the airplane during the given time period. Orders of all the customers are known in advance. Of course, not all orders can be accommodated and some orders have to be declined. Eugene LAWLER, the Chief Scientific Officer of ABEAS Corp would like to maximize the profit of the company.
You are requested to compute an optimal solution.
Consider for instance the case where the company has 4 orders:
- Order 1 (start time 0, duration 5, price 10)
- Order 2 (start time 3, duration 7, price 8)
- Order 3 (start time 5, duration 9, price 7)
- Order 4 (start time 6, duration 9, price 8)
The optimal solution consists in declining Order 2 and 3 and the gain
is 10+8 = 18.
Note that the solution made of Order 1 and 3 is feasible (the airplane is rented with no interruption from time 0 to time 14) but non-optimal.
The first line of the input contains a number T ≤ 30 that indicates the number of test cases to follow. The first line of each test case contains the number of orders n (n ≤ 10000). In the following n lines the orders are given. Each order is described by 3 integer values: The start time of the order st (0 ≤ st < 1000000), the duration d of the order (0 < d < 1000000), and the price p (0 < p < 100000) the customer is ready to pay for this order.
You are required to compute an optimal solution. For each test case your program has to write the total price paid by the airlines.
Input: 1 4 0 5 10 3 7 14 5 9 7 6 9 8 Output: 18Warning: large Input/Output data, be careful with certain languages
I feel something is wrong with the test cases. I am sure my solution is right, still it is giving me WA. I have used weighted Job Scheduling. Admin @Adrian Kuegel can you please confirm as many have pointed out that the test cases are weak.
easy dp, linear search also works
MD. Shakhawat hossain sajal:
why need binary search ???
alternate way::::: use weighted job scheduling . and if using vector do not forget to clear it .... costed me 3 wa -_-Last edit: 2016-05-19 21:09:45
is the output for your example is 42 or 43
my first dp+binarysearch..^_^
huh! 4 hr... AC in 1st
Is everything fine with the testcases? Getting WA . Pretty sure that the solution is correct.
no need for binary search linear search also works (very weak test cases).
Weighted Job Scheduling