An Interesting Dyanmic Programming + Binary Search Problem

Revision en1, by samadeep, 2023-11-04 19:05:07

An array arr of n integers is to be divided into different groups such that each element belongs to exactly one group and the size of each group is at least m.

The cost of the division is defined as the maximum value of the difference between the maximum and minimum elements of a particular group. For example, if an array [1, 2, 3, 4, 5] is divided into two groups [1, 3], [2, 4, 5], the cost is max(3 — 1, 5 — 2) = 3

Given arr and an integer m, find the minimum possible cost of dividing the array into groups of size greater than or equal to m. Example : Suppose n = 5, arr = [5, 11, 13, 4, 12], and m = 2. It is optimal to divide the array into two groups [5, 4] and [11, 13, 12] with the cost max(5 — 4, 13 — 11) = 2.

Tags dp, binary search, problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English samadeep 2023-11-04 19:05:07 788 Initial revision (published)