Finding least difference between max and min value of all possible sets of numbers

Правка en2, от NODE_SM, 2022-07-20 15:07:39

There are n arrays of k size each. a0[0],a0[1],......a0[k-1] a1[0],a1[1],......a1[k-1] . . . an-1[0],an-1[1], .... an-1[k-1] Now a Set of size n is constructed by taking any value randomly from each of the arrays. e.g one such set can be {a0[0],a1[3],a2[2],.... an-1[k-1]} My goal is to find out the min and max elements in all possible Sets such that the difference between the min and max is the lowest. Example (k=3,n=3)

[3 7 11] [1 12 15] [4 19 21] So mathematically there will be 27 such sets

(3 1 4) (3 12 4) (3 15 4) (3 1 19) (3 12 19) (3 15 19) (3 1 21) (3 12 21) (3 15 21)

(7 1 4) (7 12 4) (7 15 4) (7 1 19) (7 12 19) (7 15 19) (7 1 21) (7 12 21) (7 15 21)

(11 1 4) (7 12 4) (11 15 4) (11 1 19) (7 12 19) (11 15 19) (11 1 21) (7 12 21) (11 15 21) After computing min and max values of all these sets we can conclude that (3 1 4) is the set for which difference between min (1) and max (4) is the global minimum or lowest.

So we will output 3 as the global minimum difference and the corresponding pair which is (3 4). If there are multiple global minima then print them all. Please suggest the algorithm with better time and space complexity. We can't go for brute force approach.

Теги minheap, 2d arrays, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский NODE_SM 2022-07-20 15:07:39 808
en1 Английский NODE_SM 2022-07-20 15:06:48 499 Initial revision (published)