Hello everyone, This question was asked in Hackwithinfy (9 May 3 pm slot). Please share a possible solution.
You are the manager of the hotel and you have N customers to serve. Each customer has a happiness quotient (Ci) if the food is served to him at time x. The unhappiness of a customer is defined by |Ci — x|. You must serve all the customers and you can serve them in any order. You have to find the minimum sum of unhappiness.
Note: At a particular time only one customer is served and Each customer takes one unit of time.
Contraint:
1 <= N <=10^3 1<= Ci <=N
Sample input:
4 2 2 3 3
Sample output: 2
Sample input:
4 1 1 1 1
Sample output: 6
Please give suggestions on how to solve this problem efficiently.
Problem can be solved using DP. In the case with minimum unhappiness, customers will be served in sorted order according to their happiness quotient(C). dp[i][j] is the minimum unhappiness when we are time i and have served j people. DP has n^2 states
dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+abs(Cj-i))
Do comment if you feel something is wrong
Thank you, I understand the approach.
I don't understand the need of DP after sorting the array. Can't we simply add all the absolute difference with the index to get the answer?
Can you give a test case where this might fail?
3 3 3 Time served is not bounded by N, actual answer is (2 3 4).
Why is there dp[i-1][j] in the transition?
Edit: Sorry, I get it. You had i as time, I was thinking the opposite way.
What is the order of serving in sample input #2 to get the minimum unhappiness as 6?
How is the output of 2nd tc 6?
Any arragemenet you do, the minimum will be 7 I guess.
$$$4,1,1,1,1 -13$$$
$$$1,4,1,1,1 -11$$$
$$$1,1,4,1,1 -9$$$
$$$1,1,1,4,1 - 7$$$
$$$1,1,1,1,4 - 7$$$
How is it 6?
Hi dca, First number is size of array. Explanation of test case 2: |1-1| + |1-2| + |1-3| + |1-4| = 6
1437C - Chef Monocarp Exactly same Problem.