### prafull_vrsh's blog

By prafull_vrsh, 6 weeks ago,

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.

• +2

 » 6 weeks ago, # | ← Rev. 2 →   +12 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 Transitiondp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+abs(Cj-i))Do comment if you feel something is wrong
•  » » 6 weeks ago, # ^ |   0 Thank you, I understand the approach.
•  » » 6 weeks ago, # ^ |   +1 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? sort(C,C+n) for(i=0;i
•  » » » 6 weeks ago, # ^ |   +3 3 3 3 Time served is not bounded by N, actual answer is (2 3 4).
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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.
 » 6 weeks ago, # |   0 What is the order of serving in sample input #2 to get the minimum unhappiness as 6?
 » 6 weeks ago, # | ← Rev. 3 →   0 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?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 Hi dca, First number is size of array. Explanation of test case 2: |1-1| + |1-2| + |1-3| + |1-4| = 6
•  » » » 6 weeks ago, # ^ |   0 Oh sorry my bad. I didn't look at it clearly. Thanks for the explanation.
 » 6 weeks ago, # |   +10 1437C - Chef Monocarp Exactly same Problem.