The task in this challenge is to put elements of an array into time bins. The input will be a non-decreasing array of positive integers representing the time of events, and an integer which represents the size of each bin. Let us start with an example. We call the input array
A and the output array
`A = [1,1,1,2,7,10]` and `bin_size = 2`. `O = [4,0,0,1,1]`.
Why? With a
bin_size = 2, we'll have the following intervals:
(0,2], (2,4], (4,6], (6,8], (8,10], where four items
(1,1,1,2) are within the first interval
(0,2], none in the second and third intervals, one
7 in the interval
(6,8], and one
10 in the interval
Your code should consider every interval of length
bin_size starting from
0 and count how many numbers in
A there are in each. You should always include the right hand end of an interval in a bin so in the example above
2 is included in the count of
4. Your code should run in linear time in the sum of the lengths of the input and output.
`A = [1,2,7,12,15]` and `bin_size = 5`. `O = [2, 1, 2]`. `A = [1,2,7,12,15]` and `bin_size = 3`. `O = [2,0,1,1,1]`.
You can assume that input and output can be given in any format you find convenient. You can use any languages and libraries you like.