给定n对数字,选择k对,使得最小值和最大值之间的差异最小.请注意,1对中的2个数字不能分开.示例(n = 5,k = 3):
INPUT OUTPUT (return the index of the pairs)
5 4 1 2 4
1 5
9 8
1 0
2 7
在这种情况下,选择(5,4)(1,5)(1,0)将得到5的差异(最大值为5,min为0).我正在寻找一种有效的方式(n log n)来做这个,因为输入将非常大,我不想经历所有可能的情况.
谢谢.
注意:不需要代码.对解决方案的解释就足够了.