If the batch processing time limit is set to say 20,...
So I assume that there is no element greater than batch processing time limit. Here is my approach:
- Firstly sort the items. Then get 2 pointers for the list, one is at index 0 (left-pointer) and the other one at the last index (right-pointer).
- Take the element of right-pointer and add it to a sublist. Take the element of left-pointer and add it to the same sublist. If the sum of the elements in sublist is less than limit, update left-pointer (set it to next element) and try adding it. Continue this process until a sublist is filled.
- Then start filling the next sublist. Consume all elements to construct sublists.
Implementation in Java:
int[] input = { 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 }; // Input items.
Arrays.sort(input); // Sort the items.
int left = 0, right = input.length - 1; // Left and right pointers.
int remainder = 0, limit = 20;
// list of groups.
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
while (right >= left)
{
ArrayList<Integer> subList = new ArrayList<Integer>();
list.add(subList);
// Add the current maximum element.
subList.add(input[right]);
if (right == left)
break;
remainder = limit - input[right];
right--;
// Add small elements until limit is reached.
while (remainder > input[left]) {
subList.add(input[left]);
remainder = remainder - input[left];
left++;
}
remainder = 0; // Reset the remainder.
}
Printing the groups:
for (ArrayList<Integer> subList : list)
{
for (int i : subList)
System.out.print(i + " ");
System.out.println();
}
Output: (Each line denotes a group of numbers)
18
15 3
11 4
9 7
9 8
8