algorithm - Group numbers into closest groups -

for example, have numbers 46,47,54,58,60, , 66. want make group them in such way make largest possible group sizes. numbers grouped if values within plus or minus 10 (inclusive). so, depending on number start with, example there can 3 possible outcomes (shown in image).

what want second possible outcome, occur if started 54, numbers within 44 64 grouped, leaving 66 itself, , creating largest group (5 items).

i realize brute force example, have long list of numbers , needs across thousands of numbers.. can tell me algorithms should reading or give me suggestions?

you can sort array first. every th number can binary search find right number that's within ith number + 20 range, let position of such right index x. have find largest (x-i+1) ith numbers , done :)

runtime analysis: runtime algorithm o(nlgn), n number of items in original array.

a better solution: let's assume have array ar[] , ar[] has n items.

1. sort ar[] in non decreasing order
2. set max_result = 0, set cur_index = 0, i=0
3. increase while
4. set max_result max(max_result,i-cur_index+1)
5. set cur_index=cur_index+1
6. if cur_index

runtime analysis: o(n), n number of items in array ar[] cur_index iterate through array once , iterate once too.

correctness: array sorted in non decreasing order, if i < j , j < k , ar[i]+20 > ar[k] ar[j]+20 > ar[k] too. don't need check these items checked previous item.