Que1
You are given n problems of varying difficulty as homework. This homework is to submitted in exactly h days of the holidays.
The problems are given to you in an order and must be submitted in order, That is, before solving the question at index q, all problems at index p, where p<q should be finished.
You must submit atleast 1 problem every day, including on the last day. The teacher is a sadist and does not allow for finishing the homework early.
The difficulty of a day is the difficulty of the most difficult problem solved on that day. The difficulty of the holidays is the sum of difficulty of all days.
Optimize the way you solve the problems and return the minimum possible difficulty with which you can spend your holidays. If it is not possible to solve the problems in a way that satisfies the constriants,return -1.
1<=n<=750(you may get almost 750 problems as Homework),
0<=di<=1000(difficulty of each problem is an integer b/w 0 and 1000)
1<=h<=30 (the holidays are long and may last upto 30 days)
Ex:1
problems:[3,5,7,2,1,8,3,3,3] h=4
Day 1: 3,5,7,2,1,8 [8]
Day 2: 3 [3]
Day 3: 3[3]
Day 4:3[3]
answer=8+3+3+3=17
Ex:2
problems:[3,1,1,1,8] h=3
day1=3[3]
day2=1,1,1[1]
day3=8[8]
answer=3+1+8=12
Ex:3
problems:[1,1,1,2,1,1,9] h=8
answer=16.
Question 2
Bob the builder has built N numbers of buildings. Each buildings has a certain floor area and a price tag. Bob wants to sell exactly K of his buildings.
He further wants to maximize the total price per floor area of the selected K buildings.
For Example, if K=3 and bob sells buildings A,B,C, then the price per floor is (price[A]+price[B]+price[C])/(area[A]+area[B]+area[C])
Since Bob is only good at building stuff and not much at programming, he needs your help in figuring out the maximum price per floor area he can get if he sells exactly K buildings.
You need to return floor(answer*10^6).
Constraints::
1<=N<=1000
1<=K<=N
1<=areas[i]<=10^6
1<=price[i]<=10^6
Example:1
N=4
K=2
areas=[1,4,3,2],
prices=[2,4,6,8],
O/P: 3333333
Bob can sell building 1 and 4. Total price will be 10 and total area will be 3. That makes the price 10/3=3.333333..floor(3.33333 * 10^6)=3333333.
No other option will give a higher price per area.
**Please link similar questions if any on LC in comments or solution approach in comments **.