How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?

by

Use binary search.

Let max sum range from 0 to sum(array). So, mid = (range / 2). See if mid can be achieved by partitioning into k sets in O(n) time. If yes, go for lower range and if not, go for a higher range.

This will give you the result in O(n log n).

PS: if you have any problem with writing the code, I can help but I’d suggest you try it first yourself.

EDIT:
as requested, I’ll explain how to find if mid can be achieved by partitioning into k sets in O(n) time.

Iterate through the elements till sum is less than or equal to mid. As soon as it gets greater than mid, let it be part of next set. If you get k or less sets, mid is achievable, else not.

More Related Contents:

  1. Custom Weighted Scale [closed]
  2. Finding all possible combinations of numbers to reach a given sum
  3. How to convert floats to human-readable fractions?
  4. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  5. Why is quicksort better than mergesort?
  6. Data structures for loaded dice?
  7. Pseudorandom Number Generator – Exponential Distribution
  8. Natural Sorting algorithm
  9. What is the fastest integer factorization algorithm?
  10. How to round floats to integers while preserving their sum?
  11. True random number generator [closed]
  12. Modulus power of big numbers
  13. Is there an algorithm for color mixing that works like mixing real colors?
  14. How to find two most distant points?
  15. Efficiently reverse the order of the words (not characters) in an array of characters
  16. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  17. What is a bubble sort good for? [closed]
  18. Compute rank of a combination?
  19. Efficiently selecting a set of random elements from a linked list
  20. Skip List vs. Binary Search Tree
  21. reconstructing a tree from its preorder and postorder lists
  22. Best way of calculating n choose k?
  23. How to understand the dynamic programming solution in linear partitioning?
  24. Generating shuffled range using a PRNG rather than shuffling
  25. Randomly choosing from a list with weighted probabilities
  26. Path generation for non-intersecting disc movement on a plane
  27. Algorithm for permutations of operators and operands
  28. Tournament bracket placement algorithm
  29. How to convert decimal fractions to hexadecimal fractions?
  30. Best algorithm for matching colours.

Leave a Comment