Problem: There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
Example:
Input: [2, 1, 0, 2, 3, 1, 6] Output: 14 Explanation: You can allocate 3, 2, 1, 2, 3, 1, 2 candies respectively.
Approach: Looks like Trapping water problem. We can use the same approach here.
public static int Candy(int[] ratings)
{
int[] candies = new int[ratings.Length];
System.Array.Fill(candies, 1);
for (int i = 1; i < ratings.Length; ++i)
{
if (ratings[i] > ratings[i - 1])
{
candies[i] = candies[i - 1] + 1;
}
}
int totalCandies = candies[candies.Length - 1];
for (int i = candies.Length - 2; i >= 0; --i)
{
if (ratings[i] > ratings[i + 1])
{
candies[i] = Math.Max(candies[i], candies[i + 1] + 1);
}
totalCandies += candies[i];
}
return totalCandies;
}
No comments:
Post a Comment