CODEWITHSUNDEEP
algorithmgeometry
code geass
code geass

Reputation: 109

How to find the minimum number of groups needed for grouping a list of elements?

For example:

There is a list of elements, e.g. a sorted integer list {1,2,3,4,6,8,11}.

I want to find the minimum number of groups, in which each member in the group have a qualified difference between each other, e.g. less than or equal to 2 to each other.

In this case, we can see the answer should be 4, and one possible solution is {1,2,3},{4,6},{8},{11}.

How to write the algorithm to find the minimum number?

Furthermore, we can consider this in 2 dimension:

There is a list of points {(3,3),(3,6),(6,9)}. What is the minimum number of squares with length 3 I will need to use to cover all those points? The answer should be 2 here. But how to find it by programming?

I am asking this question for solving the question Square Fields in Google Code Jam Practice Contest, but any answer solving the first part of this question is good enough for me.

Upvotes: 1

Views: 4269

Answers (1)

timrau
timrau

Reputation: 23058

For 1-D: Sort the elements by ascending order, and greedily form groups by setting the new group's left bound as the smallest element not yet covered by any group.

Upvotes: 2

Related Questions