Kindergarten Adventures
Another use case of a range array.
Problem
Kindergarten Adventures | HackerRank
Help Meera collect the drawings in a way that lets as many students finish as is possible.
Answer
Initialization
Prepare an array of length n, called range array alongside the input array.
1st iteration
t[1]=5. Calculate the range of possible x, the starting point for Meera which lets student 1 finish their drawing when she comes to them. In this case, it is from 2 to 5. So update the range array as rangeArray[2]++ and rangeArray[6]--.
2nd and 3rd iterations
Do the same thing as we did in the first iteration for the rest of the iterations.
4th iteration
Note that, the range of possible x crosses over the 1st student. In order to represent this in the range array, we not only increment rangeArray[5] but also rangeArray[1].
All the iterations
Summarizing Step
Calculate the running sum for the range array. The answer is the index of the maximum number in the running sum array.
