1

I have a list of numbers: 0,1,2, 200,220,240, 310,330, 371,380,390

I want to put these numbers into four buckets using range with value 40 for example. 0,1,2 are all in range 40. So they should be bucketed together

200,220,240 - same story

301,330 - are in range 40

371,380,390 should be bucketed together.

I don't know how many numbers I would get or how many buckets I would need. I know only range value.

I'm looking for the minimum number of buckets with range R which will contain all numbers in some list of n numbers

I hope there are some algorithms for doing it. Could you please give some pointers? Thanks!

Capacytron
  • 113
  • Not sure I understand your question. Are you looking for the minimum number of buckets with range $R$ which will contain all numbers in some list of $n$ numbers? – Jens Sep 05 '18 at 17:15
  • Yes, thank you, your problem summary sounds much better and cleaner. – Capacytron Sep 05 '18 at 21:02

1 Answers1

1

Say $m$ is the least number in our list. Then there must be a minimum list of buckets that includes the bucket $[m,m+R]$ where $R$ is the range. This bucket can't move any further to the right, since it will then not include $m$, and moving the bucket to the left wouldn't add anything, since it already contains the least element. Then we look at our list of elements not yet included in buckets, let $m_2$ be the least element in that list, and repeat. You can always just find a minimum list of buckets by including the bucket that contains the least uncovered element as its left endpoint, and repeat until you cover every element.

Kevin Long
  • 5,159